BigFloat로 Pi를 구해보자-3. 곱셈 구현 + 10진수로 출력하기

Posted by 적분 ∫2tdt=t²+c
2012.10.18 01:24 프로그래밍/Multi precision


저번 글에서는 간단하게 덧셈과 곱셈을 구현해보았는데요, 이번에는 곱셈을 구현해보고 합니다. 이번에도 곱셈을 처음배우는 아이에게 곱셈을 가르쳐주듯, 컴퓨터에게 차근차근 가르쳐봅시다.

a = a_0 . a_1 a_2

b = b_0 . b_1 b_2 라고 했을때 이 두 수의 곱셈은 다음과 같이 계산됩니다.


예전에 곱셈공부할때가 새록새록 생각나지요??

c = ab라고 하면,

c_0 = a_0 b_0

c_1 = a_0 b_1 + a_1 b_0

c_2 = a_0 b_2 + a_1 b_1 + a_2 b_0

c_3 = a_1 b_2 + a_2 b_1

c_4 = a_2 b_2

가 됩니다. (편의상 각 자리에서 일어나는 받아올림은 생략했습니다... 만 물론 당연히 이것도 계산해주어야겠지요.)


n자리 짜리 두 수를 곱하는데는 총 n*n번의 곱셈이 필요하다는 것과, 곱셈 결과는 자릿수가 늘어난다는것 (거의 2배로 늘어나지요...) 을 알수 있었습니다. 그럼 알고리즘을 어떻게 세울지 구상을 해봅시다.


1. 곱셈결과를 저장할 c을 만들고 깨끗하게 0으로 세팅합니다.

2. 모든 i,j쌍에 대해 a_ib_j를 가져와서 곱하고, c_(i+j)자리에 더해줍니다.

3. c를 출력하면 끝


자 이제 코드를 작성해볼까요?





이번에도 도우미함수부터 정의했습니다~~

구현을 보면 알수있지만, 역시나 계산결과가 자리수를 넘어가면... 과감하게 무시할수 밖에 없습니다. (지못미 ㅠㅠ)

이제 진짜 곱셈함수를 구현해볼까요




중간에 이상한 함수가 하나 불쑥 들어가 있습니다. __emulu 함수인데, 이 함수는 어셈블리어 명령 하나와 대응됩니다. 이런함수를 intrinsic함수라고 합니다. 원래 32비트 정수 둘을 곱하면 64비트의 결과가 나오게 되지요. 하지만 c/c++언어의 기본 곱셈연산자는 상위 32비트는 버리고, 하위 32비트만 결과로 남깁니다. __emulu함수는 두 32비트 정수를 곱해서 64비트 결과를 내주는 함수이지요. 얘는 부호없는 버젼이고, 부호있는 정수일 경우에는 __emul을 사용하면 됩니다.

이런 intrinsic함수를 사용하려면 <intrin.h> 헤더를 include해주고, #pragma intrinsic(__emulu)와 같은 전처리표시자를 넣어주어야합니다.


또 보면 for문에서 0 에서 size-1까지 가는게 아니라, size-1에서 0까지 거슬러 올라오고 있는데, (순서는 결과에 영향을 미치지 않습니다만) 이는 우리가 제일 윗자리를 0번 인덱스에, 아랫자리일수록 인덱스 번호가 커지도록 정의했기때문입니다. 아랫자리부터 곱해서 더해나가야지 혹시나 일어날 받아올림을 최소화할수 있기때문이지요.


곱셈을 구현했으니, 이제 10진수로 출력을 할수 있어요~~!



보면 알수있듯이 2^32진수로 저장되어있는 수치를 10진수로 바꾸는 일은 금방 끝나는 일이 아닙니다... (정밀도가 높아질수록 곱하는 횟수도 늘어나야하지요... ㅠㅠ) 곱셈대신 비트연산자와 덧셈을 이용하는 방법도 있습니다. 이런건 나중에 천천히 알아보도록 하지요.


전체코드보기


Tags
이 댓글을 비밀 댓글로