나의 큰 O는 log x야

생각해보니 BigFloat 라이브러리를 입대전까지 심심풀이로 개발하다가 그대로 방치해두었었군요.블로그를 재정비하면서 그간 포스팅했던 소스코드의 + 기호가 공백으로 바뀌어버리는 참사가 발생해서 포스팅의 소스코드를 활용할 수 없게되었다는 소식을 받고선 아예 통으로 예전에 작업했던 코드를 공유합니다. 작업 중이던 녀석이고 공개하려고 생각도 안해서 주석도 거의 안 달리고 코드가 이쁘지도 않습니다.그래도 꼭 필요하신 분들께는 도움이 되지 않을까 싶어서 공유하오니 무단으로 가져다가 '이거 다 제가 짰습니다!' 하시지만 않으면 됩니다. (중간중간에 버그가 있어서 통째로 가져가서 쓰시면 문제가 발생할수도 있구요) 임의정밀도 실수 연산에 대해서 구현된 것들은 다음과 같아요덧셈, 뺄셈크기 비교곱셈, 카라슈바 곱셈곱셈 후 ..

프로그래밍/Multi precision 2016. 11. 4. 16:24

앞서 O(nm) 시간에 수행되는 나눗셈 알고리즘에 대해서 다뤄봤는데요, 이번엔 분할정복(Divide and Conquer)을 사용하여 나눗셈 속도를 끌어올리는 방법에 대해서 알아봅시다. 이 알고리즘은 앞서 소개했던 1998년 [Fast Recursive Division]이라는 논문에 제시된것으로, 4n by 2n 나눗셈과 3n by 2n 나눗셈으로 이뤄져있습니다. 알고리즘에 들어가기에 앞서 표기법을 정리하도록하죠. 위치기수법으로 [a3, a2, a1, a0]는 a3*X^3 + a2*X^2 + a1*X + a0 를 나타낸다고 약속합시다. 즉 10진법으로 [3, 6, 8, 7]이라는 건 3687를 나타낸다는거죠.간편한설명을 위하여 나누는 수 B는 정규화되어있다고 가정했습니다. 알고리즘 I. 4n자리 수 A를..

프로그래밍/Multi precision 2014. 4. 16. 17:23

http://bab2min.tistory.com/227http://bab2min.tistory.com/408 앞서 여러 글에서 나눗셈이 생각보다 복잡한 일이라는 걸 반복해서 언급했었는데요, 그렇다고 해서 빠르게 나눗셈을 계산하는 방법이 없다던가 그런것은 아닙니다. 곱셈을 빠르게 하는것처럼 나눗셈 역시 빠르게 계산하는 알고리즘이 존재합니다. 이 포스팅은 다음 글들을 참조해서 작성되었음을 명시하는 바입니다. * 도널드 크누스, [[컴퓨터 프로그래밍의 예술 - 2. 준수치적 알고리즘]]* Christoph Burnikel Joachim Ziegler, [Fast Recursive Division] 우리가 긴 나눗셈을 할때 제일 처음 하는 것은 몫으로 어떤 숫자가 들어갈지를 적당히 추측해내는것입니다. 뭐 사람은..

프로그래밍/Multi precision 2014. 4. 16. 03:54