나의 큰 O는 log x야

앞서서 덧셈과 뺄셈을 구현해보았는데요, 이미 둘을 구현했다면 곱셈을 구현하는 것은 생각보다 간단합니다. 알고리즘에 대해서는 다음을 참조하시면 됩니다. 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

이 카테고리에 글 쓰는것도 참 오랜만이네요!예전에는 BigInt를 구현했었고, 그 다음에는 BigFloat(실제로는 고정소수점 방식이었지만...)을 구현해서 Pi를 계산했었지요. 하지만 정수 방면으로도 다중 정밀도 소수점 이하로도 다중 정밀도를 깔끔하게 구현하는건 포스팅하지 못했지요. 전에 정말 부동소수점 포맷을 따라서 부호, 지수부와 가수부를 가지는 부동소수점 구조체를 만들고, 이를 통해서 다중정밀도 연산을 수행하는 프로그램을 짠적이 있었는데, 부동소수점이라는 특징 때문에 덧셈 뺄셈할 때마다 소수점을 맞추기 위해 Shift Left했다가 Shift Right했다가... 시프트만 계속하느라 시간을 낭비해서 연산속도가 생각보다 느려서 실망하고 때려치웠답니다... (BigFloat 구현이 부동소수점이 아니라..

프로그래밍/Multi precision 2013. 10. 26. 20:17

저번 연재에서는 코사인 함수를 이용하여 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

저번 연재에서 아크탄젠트 급수를 이용해서 Pi를 계산해보았는데, 머리를 조금 더 굴리면 훨씬 더 빠른 알고리즘을 만들어낼 수 있습니다. 가장 대표적인 공식은 다음과 같아요. John Machin이 1706년에 발견한 급수인데, Machin의 이름을 따서 Pi를 계산해내는 일련의 아크탄젠트 공식들을 Machin-like 공식이라고 부릅니다. 그냥 지나가면 재미없으니, 저 공식이 어떻게 유도되었는지 거슬러 올라가봅시다. (복소수를 이용한 증명을 소개하니, 이해하려면 복소수에 대한 기초적인 지식이 필요해요..) ...(식1) 복소수 지수를 다루는 데 가장 중요한 공식이지요. 여기서 앞의 er는 복소수의 절대값(크기)이라 하고, theta는 편각이라고 합니다. (복소평면에 그려보면 x축과 이루는 각이 theta..

프로그래밍/Multi precision 2012. 11. 22. 01:38