나의 큰 O는 log x야

곱셈은 앞서(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

앞서서 덧셈과 뺄셈을 구현해보았는데요, 이미 둘을 구현했다면 곱셈을 구현하는 것은 생각보다 간단합니다. 알고리즘에 대해서는 다음을 참조하시면 됩니다. 2012/10/18 - [프로그래밍/Multi precision] - BigFloat로 Pi를 구해보자-3. 곱셈 구현 + 10진수로 출력하기 제일 단순한 방법으로 곱셈을 구현하면 n길이인 정수에 대해 O(n^2) 시간에 계산을 완료할 수 있습니다. 더 빠른 알고리즘 구현은 일단 추후로 미루고ㅋ 당연하겠지만 지수부와 정수배열로 표현된 두 수의 곱은 정수배열끼리는 곱하고 지수부는 더하면 됩니다. 부호연산은 자명하니 설명이 필요없구요. 바로 코드를 보시죠. // xl_mul : a와 b의 곱을 구하여 dest에 저장한다 void xl_mul(PXLARGE de..

프로그래밍/Multi precision 2013. 11. 26. 12:05

두 정수배열을 가지고 더하고 빼는건 이미 앞에서 여러번 구현했었죠. 그 코드 거의 그대로 사용합니다. 2012/11/05 - [프로그래밍/Multi precision] - BigFloat로 Pi를 구해보자-8. 어셈블리어로 최적화하기2012/10/16 - [프로그래밍/Multi precision] - BigFloat로 Pi를 구해보자-2. 덧셈, 뺄셈 구현하기 위 글을 참고하시면 됩니다. 차이점은 위의 글의 코드에서는 높은 번지수에서 낮은 번지수로 내려가며 연산을 했지만, 이번에는 낮은 번지수에서 높은 번지수로 올라가며 연산을 한다는 겁니다. (이는 낮은 번지수가 낮은 자릿수를 나타내기로 했기때문이죠)코드가 길어서 접어뒀습니다. 두 정수배열을 더하는 i_adds 함수. 덧셈 결과가 오버플로우되면 1을 리..

프로그래밍/Multi precision 2013. 11. 25. 00:45

잠깐 수학 시간 ! 모든 유리수(메모리가 유한한 관계로 무리수를 포함할 실수를 완벽하게 표현하는건 불가능하겠죠)는 다음과 같은 형태로 표현 가능합니다. (a는 적절한 정수, p는 적절한 (정수)단위수, e는 적절한 (정수)지수) 이 말은 즉 a와 p와 e 값과 부호를 담으면 (메모리가 허용하는한) 모든 유리수를 표현할 수 있다는 말이 되겠죠. p는 컴퓨터 연산에 적합하도록 2의 제곱수로 고르면 편하겠죠. 32비트CPU에 맞춰서 p를 2^32로 잡으면 연산시에 간편하고 좋겠죠. 지수부 e는 32비트 정수 하나로도 충분히 표현가능합니다. -21억 정도에서 +21억 정도까지가 가능한데, 이 지수부로 표현가능한 값은 다음과 같으니까요 작을 경우 소수점 아래로 200여억 자리, 클 경우 소수점 위로 200여억자리..

프로그래밍/Multi precision 2013. 11. 20. 23:51

사실 이 프로젝트는 전에 구현했던 RealReal BigFloat가 사실은 BigFloat가 아닌 고정소수점 방식에 정수부도 2^32-1 까지 밖에 지원하지 못한다는 한계를 해결하기 위해 시작되었습니다. 그래서 진짜 BigFloat 구현하기라고 제목을 붙이고, 그동안 다중정밀도 관련 코딩을 수없이 하면서 쌓였던 모든 노하우와 기술을 적용해보기로 했습니다. 목표는1. 부동소수점 방식으로 수를 표현하도록 한다.2. 정밀도가 연산 과정에서 자연스럽게 확장될 수 있도록 한다.3. 전에 구현했던 RealReal BigFloat과 비슷한, 혹은 그 이상의 성능을 내도록 한다.4. 외부 라이브러리의 도움 없이 직접 짜본다.입니다. 이전에 제가 구현한 BigInt나 RR BigFloat는 초기에 정밀도 사이즈를 입력받..

프로그래밍/Multi precision 2013. 11. 20. 22:36

저번 연재에서는 코사인 함수를 이용하여 Pi계산속도를 비약적으로 끌어올렸었죠. 하지만 그게 최종 보스가 아닙니다. 수학자들은 수학자들답게 Pi를 구하는 무시무시한 알고리즘을 개발해냈는데, 이름만 들어도 무서운 가우스-르장드르 알고리즘(Gauss-Legendre algorithm) 입니다. 위키에도 잘 설명되어있지만, 굳이 간단하게 소개하자면 다음과 같아요. 먼저 초기값을 다음과 같이 줍니다. 그리고 아래 점화식에 따라 다음 항들을 차례로 계산해줍니다. 그러면 n이 커짐에 따라 다음값은 Pi에 수렴합니다. 으아... 전혀 이해가 되지 않는 알고리즘입니다. 산술-기하 평균의 극한이 1종 타원 적분과 연관있다는 사실을 이용하는 알고리즘이라는데... (솔직히 잘 모르겠어요 어려워요ㅠ) 중요한건 이 알고리즘은 n..

프로그래밍/Multi precision 2012. 12. 1. 15:25

저번 연재까지는 아크탄젠트 급수와, 이를 이용한 Machin 급수로 Pi를 계산하는 방법에 대해서 다뤘습니다. 이번에는 저번 방법보다 훨씬 빠른 코사인 함수를 이용한 계산법에 대해서 소개합니다. 위 점화식은 n이 무한히 커짐에 따라 Pi/2에 수렴합니다. x 값의 정밀도가 어느 정도인지에 상관없이 항상 그보다 더 정밀한 근사값을 계산해줍니다. 오차가 얼마나 빨리 줄어드는지 계산해 볼까요? 오차를 입실론이라고 하면 다음과 같이 식을 세울 수 있습니다. 함수 꼴로 바꿔보면 조금더 보기 쉽겠네요 테일러 급수를 이용하면 다음 사실이 자명함을 알 수 있습니다. 그러므로 역시 다음도 성립합니다. 즉 오차는 매 반복마다 세제곱 한것보다 더 줄어듭니다. 다르게 말하면, 매 반복마다 정밀도가 최소 3배씩은 증가한다는 말..

프로그래밍/Multi precision 2012. 11. 26. 00:19