[완료] BigInt 구현에 관한 질문..
글쓴이: senah / 작성시간: 수, 2009/04/01 - 1:53오후
음, 64비트 이상의 수치 자료형을 구현해야 할 필요가 있는데요.. long long은 C99에서는 표준이지만, 아직 C++에서는 표준으로 들어오지 않았고, Visual C++과 gcc에서 long long형에 대한 비트 조작이 조금 차이가 나는 부분이 있어서 그렇습니다. 그리고 64비트만 아니라, 128비트나 그 이상의 정밀도가 필요한 부분도 있어서 그렇습니다. (특히 부동소수점)
이미 구현되어 있는 BigInt들을 보면, 내부에 이진 자리수를 저장하는 배열을 가지고 있고, 이 배열에 대해서 비트 조작을 하게 됩니다. 그런데, 이렇게 되면 배열의 자료형을 아무리 작게 선언한다고 하더라도 1바이트의 크기를 가지고, 64비트 자료형을 구현한다고 하면 64바이트의 크기를 가지기 때문에, 좋은 구현은 아닌 것 같습니다.
다른 방법으로는 32비트 자료형 2개를 합쳐서 union으로 구현하는 방법을 생각해 볼 수 있는데, 기본 자료형의 크기를 벗어나는 수치값을, 나눠진 두 32비트 크기의 자료형에 정확하게 담는 방법이 잘 떠오르지 않네요.
BigInt와 같은 자료형을 구현해 보신 분 계신가요?
Forums:
이미 구현된 라이브러리가 다 그렇게 만들어져 있지는 않습니다.
쉽게 사용하려면 GNU MP Bignum Library를 쓰시면 될 듯 합니다.
속도도 빠르고 직접 구현하는 것 보다는 훨씬 안전합니다.
큰 수의 곱셈이나 나눗셈은 초등학교 때 배우던 방법과 동일하게 하면 됩니다.
다만 올림 수의 크기가 0~9가 아니라 0 ~ (2^32 - 1)이 되는게 다를 뿐입니다.
(32비트 자료형을 사용했을 때를 가정할 경우)
감사합니다.
가져다 쓰는 것이라면 문제가 없지만, 구현을 해보려고 합니다. 소스포지에서 이런저런 라이브러리들을 살펴봤지만 마음에 드는게 없었는데, 한번 GMP를 살펴봐야 겠습니다. 소스를 한번 뜯어봐야 겠네요.
좋은 라이브러리 알려주신거 감사합니다. :)
이진수 배열이
이진수 배열이 아니라 65536진수 배열을 쓰면 되지 않을까요?
댓글 달기