e의 연분수 전개시 특정 수렴값의 분자의 합

 

풀어보는 김에 오일러 프로젝트를 하나 더 풀어보기로 했다.

이전 문제랑 비슷해보이지만, 실은 훨씬 간결한 문제다.

 

문제에서 자연대수 e의 연분수 전개를 설명해줬고, 특정 자리까지 계산했을 때의 수렴값만 계산하면 된다.

\( a + \frac {1}{ \frac {c} {b} } = \frac {a c + b} {c} \)를 반복해서 계산하기만 하면 된다는 뜻임.

 

참 쉽죠?

 

이걸 C++ 코드로 작성하면 아래와 같다.

 

void ConvFraction(const unsigned a, const unsigned b, const unsigned c, unsigned& bN, unsigned& cN)
{
  if (!b) {
    bN = 1;
    cN = a;
  }
  else {
    bN = c;
    cN = a * c + b;
  }
}

 

이걸 반복해서 호출하는 함수만 만들어주면 큰 작업은 끝난다.

 

void Conv2Fraction(const unsigned* pVals, const unsigned cnt, unsigned& numerator, unsigned& denominator)
{
  if (!pVals || !cnt) {
    numerator = 0;
    denominator = 1;
    return;
  }

  unsigned b, c;
  b = 0;
  c = 1;

  unsigned bN, cN;
  for (unsigned i = cnt; i > 0; --i) {
    ConvFraction(pVals[i - 1], b, c, bN, cN);
    b = bN;
    c = cN;
  }

  numerator = c;
  denominator = b;
}

 

마지막으로 연분수 전개를 배열에 저장한 뒤 계산해서 화면에 출력하는 본체를 만들면 된다.

 

const static auto COUNT = 20;

int main()
{
  unsigned vals[COUNT];
  vals[0] = 2;
  for (int i = 1; i < COUNT; ++i) {
    vals[i] = ((i + 1) % 3) ? 1 : (i / 3) * 2 + 2;
  }

  printf("e = [");
  for (int i = 0; i < COUNT; ++i) {
    printf("%u", vals[i]);
    printf((i < COUNT - 1) ? (!i ? ";" : ",") : "]");
  }

  unsigned numerator, denominator;
  Conv2Fraction(vals, COUNT, numerator, denominator);

  printf(" = %lu / %lu = %g\n", numerator, denominator, (double)numerator / denominator);

  int sum = 0;
  while (numerator) {
    sum += (numerator % 10);
    numerator /= 10;
  }

  printf("sum of all digits of numerator = %d\n", sum);
}

 

20개에 대해 계산한 뒤 출력한 결과는 아래와 같다.

 

e = [2;1,2,1,1,4,1,1,6,1,1,8,1,1,10,1,1,12,1,1] = 28245729 / 10391023 = 2.71828
sum of all digits of numerator = 39

 

이제 COUNT의 값을 100으로만 바꿔 출력하면 될... 것 같지만...

 

e = [2;1,2,1,1,4,1,1,6,1,1,8,1,1,10,1,1,12,1,1,14,1,1,16,1,1,18,1,1,20,1,1,22,1,1,24,1,1,26,1,1,28,1,1,30,1,1,32,1,1,34,1,1,36,1,1,38,1,1,40,1,1,42,1,1,44,1,1,46,1,1,48,1,1,50,1,1,52,1,1,54,1,1,56,1,1,58,1,1,60,1,1,62,1,1,64,1,1,66,1] = 2183414923 / 1487564356 = 1.46778
sum of all digits of numerator = 37

 

세상이 그렇게 녹록하지 않다.

이렇게 된 원인은 간단하다.

unsigned는 저렇게 큰 값을 다룰 수 없기 때문이다.

 

C++에서 커다란 수를 다루려면 별도의 클래스를 하나 만들서서 사용해야 한다.

만들기는 귀찮고[...] 뒤져보니 BIG INTEGER WITH C++란 글이 눈에 띈다.

 

양수만 사용하도록^[각주:1] 만들어져있는데, 제곱, 제곱근은 물론 로그 함수까지 만들어진 단순하면서도 강력한 코드다.

이를 사용해서 위의 코드를 간단하게 아래처럼 수정했다.

 

#include "bigint.h"

void ConvFraction2(const unsigned a, const BigInt b, const BigInt c, BigInt& bN, BigInt& cN)
{
  if (b == 0) {
    bN = Integer(1);
    cN = Integer((int)a);
  }
  else {
    bN = c;
    cN = c * a + b;
  }
}

void Conv2Fraction2(const unsigned* pVals, const unsigned cnt, BigInt& numerator, BigInt& denominator)
{
  if (!pVals || !cnt) {
    numerator = Integer(0);
    denominator = Integer(1);
    return;
  }

  BigInt b, c;
  b = Integer(0);
  c = Integer(1);

  BigInt bN, cN;
  for (unsigned i = cnt; i > 0; --i) {
    ConvFraction2(pVals[i - 1], b, c, bN, cN);
    b = bN;
    c = cN;
  }

  numerator = c;
  denominator = b;
}

 

BigInt를 사용하여 90개^[각주:2]에 대해 계산한 결과는 아래와 같다.

 

e = [2;1,2,1,1,4,1,1,6,1,1,8,1,1,10,1,1,12,1,1,14,1,1,16,1,1,18,1,1,20,1,1,22,1,1,24,1,1,26,1,1,28,1,1,30,1,1,32,1,1,34,1,1,36,1,1,38,1,1,40,1,1,42,1,1,44,1,1,46,1,1,48,1,1,50,1,1,52,1,1,54,1,1,56,1,1,58,1,1,60]
  = 3122681731663446268852622205448790639106028937172031 / 1148770410400620419199349985370106606649752990544640
sum of all digits of numerator = 211

 

보다시피 자릿수가 너무 길어 C++에 내장된 기본 자료형만으로는 도저히 계산할 수가 없다.

 

 

1. 조만간 이걸 class로 변형해서 음수까지 처리 가능하도록 수정할 생각 [본문으로]
2. 답을 공개하는 건 선을 넘는 것 같아 90개로 제한 [본문으로]