Sqrt(2)의 수렴

\(\sqrt{2}\)는 아래와 같이 근사화시킬 수 있다.

\(\sqrt{2} = 1+\frac{1}{2+ \frac{1}{2+\frac{1}{2+\frac{1}{2+\frac{1}{ \cdots }}}}}\)

여기서, 1,000 자리까지 전개한 결과에서 분모와 분자의 자릿수가 다른 것이 몇 번 나오는가를 계산하는 문제이다.

위의 전개를 조금만 다르게 써 보면 아래와 같이 된다.

\(\sqrt{2} = 1+\frac{1}{1+1+ \frac{1}{1+1+\frac{1}{1+1+\frac{1}{1+1+\frac{1}{ \cdots }}}}}\)

이렇게 하면 첫번째 전개에서의 분모/분자를 두 번째 전개의 특정 부분에 쉽게 적용할 수 있다.

1,000 자리까지의 전개 결과를 화면에 출력하려면 대략 아래와 같…으면 좋겠지만, 현실은 시궁창.

#include <stdio.h>

void getNextVal(unsigned &numerator, unsigned &denominator)
{
    // 1+1/(1+num/denom)
    numerator += denominator;
    numerator ^= denominator ^= numerator ^= denominator;
    numerator += denominator;
}

int main(int argc, char* argv[])
{
    unsigned numerator = 1;
    unsigned denominator = 1;
    for (int i = 0; i < 1000; i++) {
        getNextVal(numerator, denominator);
        printf("%u / %u\n", numerator, denominator);
    }

    return 0;
}

문제는 자릿수다.

32비트 정수는 9자리까지밖에 표현할 수 없고, 64비트 정수를 적용해도 18자리가 한계다.

C/C++에서는 이렇게 긴 자리를 적용하려면 배열이나 벡터 등을 사용해야 한다.

벡터를 사용해 작성한 코드는 아래와 같다.

#include <stdio.h>
#include <vector>

using namespace std;

// 8자리씩 저장
const unsigned maxDigit = 99999999;

class bigInt {
private:
    vector <unsigned> num;

public:
    bigInt(unsigned init);
    void add(bigInt a);
    void exchange(bigInt &a);
    int getLen();
};

bigInt::bigInt(unsigned init) {
    num.clear();
    num.push_back(init);
}

void bigInt::add(bigInt a) {
    while (this->num.size() < a.num.size()) {
        this->num.push_back(0);
    }
    for (vector<int>::size_type i = 0; i < a.num.size(); i++) {
        this->num.at(i) += a.num.at(i);
    }

    int len = this->num.size();
    for (int i = 0; i < len - 1; i++) {
        this->num.at(i + 1) += this->num.at(i) / (maxDigit + 1);
        this->num.at(i) %= (maxDigit + 1);
    }

    if (this->num.at(len - 1) > maxDigit) {
        this->num.push_back(this->num.at(len - 1) / (maxDigit + 1));
        this->num.at(len - 1) %= (maxDigit + 1);
    }
}

void bigInt::exchange(bigInt &a) {
    vector <unsigned> temp;
    temp.assign(this->num.begin(), this->num.end());
    this->num.assign(a.num.begin(), a.num.end());
    a.num.assign(temp.begin(), temp.end());
}

int bigInt::getLen() {
    char temp[10];

    int len = this->num.size();
    return sprintf_s(temp, 10, "%u", this->num.at(len - 1)) + (len - 1) * 8;
}

void getNextVal(bigInt &numerator, bigInt &denominator) {
    numerator.add(denominator);
    numerator.exchange(denominator);
    numerator.add(denominator);
}

int main(int argc, char* argv[])
{
    bigInt numerator(1);
    bigInt denominator(1);
    int count = 0;
    for (int i = 0; i < 1000; i++) {

        getNextVal(numerator, denominator);
        if (numerator.getLen()>denominator.getLen()) {
            count++;
        }
    }
    printf("result : %d\n", count);
    return 0;
}