나의 큰 O는 log x야

눈을 감고 사칙연산을 배우던 초등학생 때로 돌아가보면, 덧셈, 뺄셈, 곱셈, 나눗셈 중 제일 어려웠던 것은 나눗셈이었습니다. 계산속도도 나눗셈이 제일 느리고, 실수도 많이 합니다. 그건 나눗셈을 배우던 학생들이 어리석어서가 아니라 본질적으로 나눗셈이 곱셈보다 어려운 과정이기 때문입니다. 한 번의 나눗셈을 하기 위해서는 제일 높은 자리에 들어갈 숫자를 짐작하여서 곱해보고, 빼는 작업을 무수히 반복해야 합니다. 만약 n자리 수를 나눈다고 하면 최소 n번의 곱셈과 뺄셈이 필요하다는 것이지요. 그리고 결과가 나눠떨어지지 않아서 소수점 이하로 내려가면, 걸리는 시간은 몇배로 불어날지 모릅니다. 이렇게 장황하게 나눗셈에 대해서 설명한것은, 필산 나눗셈 알고리즘은 소수점 아래로 무한한 정밀도를 추구하는, 우리가 만들..

프로그래밍/Multi precision 2012. 10. 24. 00:30

저번 글에서는 간단하게 덧셈과 곱셈을 구현해보았는데요, 이번에는 곱셈을 구현해보고 합니다. 이번에도 곱셈을 처음배우는 아이에게 곱셈을 가르쳐주듯, 컴퓨터에게 차근차근 가르쳐봅시다.a = a_0 . a_1 a_2b = b_0 . b_1 b_2 라고 했을때 이 두 수의 곱셈은 다음과 같이 계산됩니다. 예전에 곱셈공부할때가 새록새록 생각나지요??c = ab라고 하면,c_0 = a_0 b_0c_1 = a_0 b_1 + a_1 b_0c_2 = a_0 b_2 + a_1 b_1 + a_2 b_0c_3 = a_1 b_2 + a_2 b_1c_4 = a_2 b_2가 됩니다. (편의상 각 자리에서 일어나는 받아올림은 생략했습니다... 만 물론 당연히 이것도 계산해주어야겠지요.) n자리 짜리 두 수를 곱하는데는 총 n*n번의..

프로그래밍/Multi precision 2012. 10. 18. 01:24

(짤방은 그냥 재미로...) BigFloat에서 덧셈과 뺄셈을 구현하기 위해서는 초등학교 다닐때의 마음으로 되돌아가서, 컴퓨터에게 받아올림과 받아내림을 알려줘야합니다.ㅋ (p = 2^32) c2 = (a2 + b2)를 p로 나눈 나머지 c1 = (a1 + b1 + 받아올림)을 p로 나눈 나머지 c0 = (a0 + b0 + 받아올림)을 p로 나눈 나머지 이런식으로 계산이 되지요. 다행히도 우리는 구현할때 a_n + b_n을 2^32으로 매번 나눠줄 필요가 없습니다. 32비트 CPU에서는 2^32를 넘어가는 숫자는 자동으로 오버플로우되어 버리기 때문이지요. 그러면 받아올림이 일어났는지는 어떻게 알수 있을까요? 실제로 CPU 어셈블리 상에서는 add연산에서 오버플로우가 발생하면, 캐리플래그(CF)가 세트되어서..

프로그래밍/Multi precision 2012. 10. 16. 01:51

기초적인 BigFloat의 수학적 원리는 다음과 같아요~ 십진법은 위와 같은 규칙으로 표현됩니다. 십진법에서의 덧셈은 각 자리수에 해당하는 숫자들끼리 더해서 받아올림을 함으로써 연산됩니다. 이를 32비트 컴퓨터에서 효율적으로 구현하기 위해서는 10진법보다는진법을 사용하는것이 좋겠지요. 이런 모양으로 실수를 표현할수 있을겁니다. 일단 이번 연재의 궁극적인 목표는 Pi값의 계산이니만큼 정수부분이 무지막지하게 큰 정수를 표현해야할 필요는 없습니다. a, b부분은 쳐내고, 다음과 같은 모양으로 표현하는게 괜찮겠네요. a0은 정수부분을 표현하는 데이터로, a1부터는 소수점 이하를 표현하는 데이터로 활용하면 될것입니다. 자 이제 이걸 바탕으로 우리의 BigFloat자료형이 될 RealReal구조체를 짜봅시다. ty..

프로그래밍/Multi precision 2012. 10. 16. 00:45

오랜만에 프로그래밍 글을 쓰네요~! 예전에 BigInt를 구현해보는 연재를 잠깐했었는데요, 이번에는 BigInt를 실수범위로 확장시킨것이라고 할 수 있는 BigFloat, 즉 메모리 용량이 허용하는 내로 무한한 소수점을 표현할 수 있는 자료형을 구현해보려고 합니다. (이전 연재: 2009/03/29 - [프로그래밍/Multi precision] - BigInteger를 구현해보자 - 1. BigInteger의 개요) BigInt 구현의 최대떡밥이 팩토리알을 계산하는것이라면, BigFloat의 최대떡밥은 Pi를 계산해내는것입니다. 그래서 이번 연재에서는 BigFloat를 구현하고, 여러가지 수치를 연산하는 방법을 탐구해보고, 궁극적으로는 Pi값을 구해내는것을 목표로 하고 있습니다. 예전에는 부동소수점 방식..

프로그래밍/Multi precision 2012. 10. 16. 00:43