BigNum

 수학관련 (또는 연구관련) 코딩을 하다보면 8바이트의 범위는 너무 좁아서 난감할 때가 많다. 스크립트 언어를 사용할 수 도 있지만, 이번에 cow문제를 풀면서 스크립트(lua)에서도 INF 가 뜨는..  괴물같은 숫자를 다뤄야했다.

하는수 없이 c++ BigNum class를 구현하게 되었다.

BigNum이란, 정수나 실수에 대해서 자릿수 제한이 없는, 이론상 무한에 가까운 수도 표현할 수 있는 타입이다.

 일반적으로 표현할 숫자를 처리할 수 있는 n자리씩 끊어서 연결시키는 구조이고, 가장 흔하게는 n=1인 상태의 노드로 구성한다. 그런데 이는 노드를 너무 많이 생성하게 되서 실제 연산중엔 조금 느린감이 있다. (계속된 동적할당..) 그래서 나는 8바이트의 공간에 4바이트만을 값을 표현하는 공간으로 썻고, 남은 4바이트는 연산시 오버플로를 방지하는 버퍼역할로써 사용했다. (m바이트의 곱 연산시 결과는 2m바이트를 넘을 수 없다.)

 조금 낭비같긴 하지만, 공간낭비보단 시간낭비가 더 아까운 요즘은 차라리 이게 더 좋은 방법일 수도 있다.

 

나는 BigNum 중 BigInt만 구현을 했고, 비슷한 방법으로 BigFloat도 구현할 수 있다.  시간이 나면 만들어봐야겠다. 

.. 그보다 만들어둔 BigInt는 급해서 너무 막 만들어둔 감이 있는데, 두고두고 쓸 수 있을정도로 수정좀 해야할 듯 하다. 그리고 비트수준으로 연산할 수 있게하면 더 빠른 연산이 가능할 것 같다. 가산기 만들듯 하면 될듯한데말이다..

BigNum.7z

딱히 좋은것도 아니고, 웹에 찾아보면 이것보다 훨씬 좋은 Big Integer라이브러리도 많지만,, 직접 만들어쓴다면 기쁨이 두배!