상세 컨텐츠

본문 제목

[진짜 BigFloat 구현하기] 0. 시작에 앞서서

프로그래밍/Multi precision

by ∫2tdt=t²+c 2013. 11. 20. 22:36

본문



사실 이 프로젝트는 전에 구현했던 RealReal BigFloat가 사실은 BigFloat가 아닌 고정소수점 방식에 정수부도 2^32-1 까지 밖에 지원하지 못한다는 한계를 해결하기 위해 시작되었습니다. 그래서 진짜 BigFloat 구현하기라고 제목을 붙이고, 그동안 다중정밀도 관련 코딩을 수없이 하면서 쌓였던 모든 노하우와 기술을 적용해보기로 했습니다.


목표는

1. 부동소수점 방식으로 수를 표현하도록 한다.

2. 정밀도가 연산 과정에서 자연스럽게 확장될 수 있도록 한다.

3. 전에 구현했던 RealReal BigFloat과 비슷한, 혹은 그 이상의 성능을 내도록 한다.

4. 외부 라이브러리의 도움 없이 직접 짜본다.

입니다.



이전에 제가 구현한 BigInt나 RR BigFloat는 초기에 정밀도 사이즈를 입력받으면 연산 결과도 그 정밀도에 맞춰져 자동으로 truncation 되었는데요, 여기서는 되도록이면 정밀도 손실을 줄이고자 연산 결과에 따라 적절하게 정밀도가 조정되도록 할 것입니다.


연산 과정 도중에 정밀도를 조정하는건 간단한 문제가 아닌데요, 수치 데이터를 배열에 담고 있었다면 배열 크기를 늘리고 재배치하는 작업이 필요하죠. 이건 배열 크기를 넉넉하게 잡으면 해결되는 문제긴 한데, 정밀도가 높은 자릿수 방향으로 늘어날 수도 있고 낮은 자릿수 방향으로 늘어날수도 있으니 배열이 양쪽으로 자랄 수 있어야합니다.


양쪽으로 자라는 배열은 없죠. 다만 deque는 양 끝쪽에서의 삽입과 삭제가 O(1)안에 가능하고, 임의 위치의 접근이 O(1)내에 가능합니다. 그래서 deque를 자료구조로 사용하는 BigFloat를 구현하기로 마음 먹었습니다. (deque는 일반적으로 환형 큐로 구현합니다.)


자세한 얘기는 다음으로 패스.

관련글 더보기

댓글 영역