TEUS.me

CBigInt 포팅 삽질기

2020. 11. 15. 21:49
 
 

이전 포스팅에서 간략히 얘기했듯이, BIG INTEGER WITH C++를 클래스 형식으로 포팅하기로 했다.

이 코드는 벡터를 사용해서 BigInt를 구현했는데, 전체적으로 코드가 간략하다는 점이 돋보였다.

 

하지만, 단점이 몇 있었는데, 무엇보다도 음수를 지원하지 않는다는 점이었다.

그 외에도 로그 함수에 오류가 있었고, sqrt 함수는 성능이 너무 느렸다...

 

포팅을 진행하며 손을 댄 내용들을 간략히 정리해본다.

 

#include <bits/stdc++.h>

원본 코드는 stdc++.h를 사용하도록 되어있다.

이 헤더는 잡다한(?) 헤더를 몽땅 포함시키는 코드인데, 실제 상황에선 그닥 쓸모가 없다.

찾아보니 대회 같은 데 나가면 쓸만하다는데, 글쎄... 잘 모르겠다...

 

간략하게 쓸 내용만 추가하는 것으로 변경.

#include <iostream>
#include <vector>
#include <string>

 

부호와 NaN 상태 추가

별도의 속성을 추가했다.

0으로 나누거나, 제곱근을 잘못 처리하는 등등의 경우에 NaN으로 설정한다.

bool bMinus;
bool bInvalid;

 

로그 함수 변경

로그 함수는 오류가 있어 통째로 변경해야 했다.

간결한 건 좋은데, 너무 간결해서 생기는 문제였다.

\(log _{31724} 471432 \approx 1.26037\cdots \) 이므로 log(31724, 471432)의 결과가 1이 나와야 하는데, 2가 나온다.

 

마침, 깃헙에서 훌륭한 코드를 찾았다.

이를 거의 그대로 사용해서 아래와 같은 메소드를 구성했다.

CBigInt CBigInt::log(CBigInt b, CBigInt n)
{
  if (b.bInvalid || n.bInvalid || (b < 2) || (n < 1)) {
    CBigInt ans;
    ans.bInvalid = true;
    return ans;
  }

  CBigInt lo(0);
  CBigInt b_lo(1);
  CBigInt hi(1);
  CBigInt mid, b_mid;

  CBigInt b_hi(b);

  while (b_hi < n) {
   lo = hi; b_lo = b_hi; hi = hi * 2; b_hi = b_hi * b_hi;
  }

  while (hi > lo + 1)
  {
    mid = (lo + hi) / 2;

    b_mid = b_lo * pow(b, mid - lo);

    if (n < b_mid) { hi = mid; b_hi = b_mid; }
    if (n > b_mid) { lo = mid; b_lo = b_mid; }
    if (n == b_mid) { return mid; }
  }

  return b_hi == n ? hi : lo;
}

 

제곱근 함수 변경

제곱근 함수는 잘 동작하긴 하지만, 동작 속도가 너무 느리다.

보통 뉴턴 법이라 부르는, 근사해가며 해를 찾는 방식을 사용하는데, 커다란 숫자에선 성능이 만족스럽지 않다.

 

이보다는 더 빠른 방법이 많이 연구되어 있어서 이를 적용했다.

CBigInt CBigInt::sqrt(CBigInt num, const bool bRoundToNearestInt)
{
  num.Set();

  if (num.bInvalid || num.bMinus) {
    CBigInt ans;
    ans.bInvalid = true;
    return ans;
  }

  if (IsZeroInternal(num) || (num == 1)) {
    return num;
  }

  CBigInt res(0);
	
  CBigInt one(1);
  while (one <= num) { one *= 4; }
  one /= 4;	// "one" bit starts at the highest power of four <= the argument.

  while (!IsZeroInternal(one)) {
    if (num >= res + one) {
      num = num - (res + one);
      res = res + one + one;
    }
    res /= 2;
    one /= 4;
  }

  /* Do arithmetic rounding to nearest integer */
  if (bRoundToNearestInt && (num > res)) { ++res; }

  return res;
}

 

소숫점 단위의 나눗셈 출력 함수 추가

이 클래스는 커다란 정수를 다루는 함수지만, 나눗셈 연산 결과를 실수 형식으로 출력하는 함수를 별도로 만들기로 했다.

프로젝트 오일러의 문제를 해결하는 과정에서 가끔 쓸 일이 있기 때문이다.

void CBigInt::printfFPdivision(CBigInt a, CBigInt b, size_t digitbelowdot, const bool printunnecessary0, const bool CRLF)
{
  if (a.bInvalid || b.bInvalid || IsZeroInternal(b)) { printf("NaN"); }
  else {
    a.Set();
    b.Set();

    if (xorbool(a.bMinus, b.bMinus)) { printf("-"); }
    a.bMinus = b.bMinus = false;

    CBigInt n = a / b;
    n.Print();

    CBigInt m = a % b;

    if (digitbelowdot && (!IsZeroInternal(m) || printunnecessary0)) {
      printf(".");

      for (size_t i = 0; (i < digitbelowdot) && (!IsZeroInternal(m) || printunnecessary0); ++i) {
        m *= 10;
        n = m / b;
        n.Print();

        m %= b;
      }
    }
  }

  if (CRLF) { printf("\n"); }
}

 

이 함수들을 실제로 적용해서 화면에 출력한 결과는 다음과 같다.

355 / 133으로 원주율을 근사하는 식의 결과를 소수점 아래 80자리까지 출력한 결과도 볼 수 있다.

참고로, 제곱근 계산에 16msec 소요된 것으로 나오는데, 제곱근 연산을 100회 반복한 결과이다.

 

 

 

공유하기

facebook twitter kakaoTalk kakaostory naver band

본문과 관련 있는 내용으로 댓글을 남겨주시면 감사하겠습니다.

비밀글모드

  1. 숫자에 대한 근본적인 연구를 많이 하시네요 ..
    제 경우 계산이 주인 프로그램 보다는 동작이 중요한 놈들이 더 많았던지라
    개인적으로 약점이라 생각하는 부분들을 많이 다루시는듯 하여
    부럽습니다 ㅎㅎ
    2020.11.24 08:29 신고
    • 칭찬 감사드립니다...
      근데, 무림 고수에게 칭찬 받는 평범한 무인 느낌입니다... ^^
      2020.11.24 14:36 신고
    • 아이차암... 고수라뇨..그리고.. 평범이라 하시기엔 다루시는 주제가 ㅎㅎㅎ
      2020.11.24 14:38 신고