상세 컨텐츠

본문 제목

환형 큐를 사용한 다중정밀도 연산

프로그래밍/Multi precision

by ∫2tdt=t²+c 2013. 10. 26. 20:17

본문



이 카테고리에 글 쓰는것도 참 오랜만이네요!

예전에는 BigInt를 구현했었고, 그 다음에는 BigFloat(실제로는 고정소수점 방식이었지만...)을 구현해서 Pi를 계산했었지요. 하지만 정수 방면으로도 다중 정밀도 소수점 이하로도 다중 정밀도를 깔끔하게 구현하는건 포스팅하지 못했지요.


전에 정말 부동소수점 포맷을 따라서 부호, 지수부와 가수부를 가지는 부동소수점 구조체를 만들고, 이를 통해서 다중정밀도 연산을 수행하는 프로그램을 짠적이 있었는데, 부동소수점이라는 특징 때문에 덧셈 뺄셈할 때마다 소수점을 맞추기 위해 Shift Left했다가 Shift Right했다가... 시프트만 계속하느라 시간을 낭비해서 연산속도가 생각보다 느려서 실망하고 때려치웠답니다... (BigFloat 구현이 부동소수점이 아니라 고정소수점이 된 이유도 여기에 있었습니다)


최근(이라 쓰고 시험기간이라 읽습니다) 이를 보완할 만한 좋은 아이디어가 떠올라서 새로 다중정밀도 연산 라이브러리를 짜보고 있습니다. 아이디어는 대략 이래요.


1. 부동소수점의 지수를 비트 단위가 아니라 워드단위(32비트 정수 혹은 64비트 정수)로 사용하면, 덧셈/뺄셈 연산할 때 굳이 시프팅을 할 필요가 없다. 

2. 가수부를 환형 큐로 저장하면, 소수점 아래 방향으로도 확장가능하고, 정수부 위쪽으로도 확장이 가능하다.


뭐 32비트 정수 배열을 가지고 덧셈 뺄셈하는건 이전에도 수없이 구현했으니깐 약간 손만 봐서 가져오면 될듯하고, 환형 큐가 끊기는 부분에서의 처리만 잘 해주면 크게 성능 저하없는 다중정밀도 부동소수점 연산을 할 수 있지 않을까 기대하고 있습니다.


성능은.... 한 번 구현을 해보고 비교해보도록 할래요.



관련글 더보기

댓글 영역