나의 큰 O는 log x야

이번글에서는 두번째 글에서 제시했던 알고리즘을 실제 사용가능하도록 개량해보도록 하겠습니다. 알고리즘 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

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

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