나의 큰 O는 log x야

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

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

원래 XFloat는 심심풀이로 c/c++용으로 개발중이던 고정밀도 부동소수점 연산 라이브러리였습니다. 그런데 사지방에서는 c/c++ 개발이 곤란한데, 고정밀도 연산이 필요한 일이 종종 생겨서, 어떡하면 좋을까하다가 예전에 개발하던걸 다시 떠올려서 Javascript용으로 다시 짰습니다. 어차피 아예 만들어버린 김에 공개하고 여러 사람들의 피드백도 받으며 더 성장하는 길을 선택하는게 좋을거 같다는 생각이 들어서 사이트를 만들고 매뉴얼도 작성해보았습니다. 짠! http://math.bab2min.pe.kr/xf-main 위 사이트에서 XFloat에 대한 정보를 얻을 수 있구요, 예제 코드 및 테스트 등도 해볼 수 있습니다. 자바스크립트 한계상 속도가 잘 안나오는건 어쩔수 없는 듯합니다. (c/c++만 줄곧해..

프로그래밍/Multi precision 2015. 9. 29. 20:25

이번글에서는 두번째 글에서 제시했던 알고리즘을 실제 사용가능하도록 개량해보도록 하겠습니다. 알고리즘 I. 4n자리 수 A를 2n자리 수 B로 나누는 알고리즘 (단 A < BX^2. 즉 몫이 2n자리 이하로 나오는 경우) 1. n자리씩 묶어서, A를 [a3, a2, a1, a0], B를 [b1, b0]이라고 합니다. 2. [a3, a2, a1]을 [b1, b0]으로 나눕니다. 몫을 q1, 나머지를 [r2, r1]이라고 합니다. 3. [r2, r1, a0]를 [b1, b0]으로 나눕니다. 몫을 q0, 나머지를 S라고 합니다. 4. 몫으로 [q1, q0], 나머지로 S를 출력합니다. 알고리즘 II. 3n자리 수 A를 2n자리 수 B로 나누는 알고리즘 (단 A < BX. 즉 몫이 n자리 이하로 나오는 경우) 1..

프로그래밍/Multi precision 2014. 4. 22. 04: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

카라슈바 알고리즘까지는 쉽게 이해했는데,톰-쿡 알고리즘은 괜히 어려워 보여서 그동안 접근하지 못했는데 사실 알고보면 단순한 거였슴다! 일반적인 곱셈 방법으로는 n자리 수 간의 곱셈을 수행하게 되면 총 n^2번의 곱셈이 필요하게 된다. 당연한 말씀.예를 들어을 곱하고자 한다면 각 자리수마다 한 번씩 곱셈을 해야하니 총 36번의 곱셈을 해야겠지요.. 근데 안드레이 톰과 스테픈 쿡이라는 학자가 발상의 전환을 했어요. (카라슈바마냥ㅋ) 숫자를 다항식으로 보고, 다항식끼리 곱하는거야 (그나마 간단한 톰-3 알고리즘을 중심으로 설명할게요.) 숫자 n과 m을 다항식으로 바꾸기 위해 3조각으로 나누도록하겠습니다. 한 조각의 단위는 100으로 잡으면 되겠네요. 자 이 조각을 계수로 이용해서 다항식을 만들어봅시다. 참 쉽..

프로그래밍/Multi precision 2014. 3. 30. 05:49

곱셈은 앞서(http://bab2min.tistory.com/405)에서 이미 구현했습니다. 다 좋은데 시간복잡도가 O(n^2)이라 숫자가 커지면 커질수록 너무 느려진다는 단점이 있죠. 하지만 이런 문제를 겪을줄 알았는지 이미 일찍이 수학자들이 여러 가지 빠른 곱셈 알고리즘을 발명해 놓았습니다. 여기에서는 곱셈 알고리즘 중 두번째로 구현이 간단한(그 댓가로 뒤에서 두번째로 빠른) 카라슈바 알고리즘(Karatsuba Algorithm)을 구현해보도록 할것입니다. 카라슈바 알고리즘의 개요는 다음과 같습니다. 2자리수 간의 곱을 계산하려면 일반적인 곱셈법으로는 한 자릿수 곱셈이 총 4번이 필요한데, 카라슈바는 한 자릿수 곱셈을 3번만 하고, 덧셈/뺄셈으로 나머지 부분의 결과를 구해내는 아이디어를 떠올립니다. ..

프로그래밍/Multi precision 2014. 3. 11. 23:54

앞서서 곱셈을 구현했으니, 이제 나눗셈을 구현할 차례겠죠?근데 문제는 나눗셈을 구현하는게 생각보다 까다롭다는거지요. 일반적으로 우리가 학교에서 배우는 나눗셈 방법은 장제법(long division)이라고 하는데,이게 얼마나 어려운지는 초등학생들이 더 잘 압니다.http://bab2min.tistory.com/54 자세한 알고리즘에 대한 설명은 위 페이지로 대신합니다.우리가 나눗셈을 할때 나누는 수랑 나눠지는 수 자리를 맞춰서 계산하죠. 자리 맞추기 위해 숫자들을 왼쪽으로 옮기고 오른쪽으로 옮기고 하는데, 2진법에서 이것과 근본적으로 같은 연산이 비트 시프트 연산입니다.다른말로 하면 나머지를 구하는 나눗셈 연산을 위해서는 먼저 시프트 연산을 구현할 필요가 있다는 거지요. void xl_setnan(PXLA..

프로그래밍/Multi precision 2014. 3. 2. 02:34