BigInteger를 구현해보자 - 7. 나누기

Posted by 적분 ∫2tdt=t²+c
2009.04.25 03:29 프로그래밍/Multi precision

초등학생 때 배웠던 나눗셈의 알고리즘이다. big integer 나눗셈에서도 이 알고리즘을 그대로 쓴다.



함수 자체가 복잡하다. 나누기를 하려면 원래 수와 나누는 수가 필요하고, 몫을 받을 놈, 나머지를 받을 놈까지 필요하다. 여기서 rmd를 원래 수 겸 나머지를 받는 놈으로 하기로 하고 함수를 짰다.
먼저 원래 수와 나누려는 수의 비트 자리수를 비교해서, 나누는 수가 큰 경우 그대로 리턴해버렸다. (어차피 몫은 0이고, 원래수가 그대로 나머지가 될테니까.)
그렇지 않을 경우에는 나누는 수를 복사해서 비트수 차이만큼 왼쪽으로 시프트해준다. 위의 그림에서 109와 123456의 자리수가 3개 차이나므로 3자리 왼쪽인 1000의 자리에서부터 나누기를 시작하는 것과 같다. 이제 rmd와 temp의 크기를 비교한다. rmd가 더 크다면 quo의 그 자리는 1이 된다. (이진법에서는 한 자리가 0 또는 1이므로 0이아니면 무조건 1이다.) 그럴 경우 rmd에서 temp를 빼준다. 123에 109가 한 번 들어가므로 123에서 109를 뺀 것과 같은 이치이다. 자 이제 자리수를 하나 낮춰서 (오른쪽으로 한 번 시프트해서) 지금 했던 것을 또다시 반복한다. 그리하여 자리수가 1의 자리까지 내려올때까지 뺄셈을 반복하고 최종적으로 남는 값이 나머지가 된다.


이 함수는 위에서 쓰였던 bigint의 비트수를 구하는 함수이다.

n자리의 나눗셈을 한다면 최소 n번의 bigint 크기비교와 n번의 시프트, 최악의 경우 n번의 뺄셈을 해야한다. 따라서 최악의 경우의 시간복잡도는 O(n^2)이 된다.
Tags
이 댓글을 비밀 댓글로
  1. bigint_div_i 함수에서요... bigint_createcopy 함수를 썼는데요... 앞에서 정의한 적이 없는 것 같은데요?? 오류가 나네요~
    divisor를 temp로 copy하는 것 같은데요..
    bigint_createcopy 대신 bigint_create(divisor->length, &temp); 를 한다음에
    bigint_set(&temp, divisor); 를 해주면 되는 것 같습니다
    • 어이쿠 createcopy함수를 빼먹었나봅니다. 님이 말씀하신대로 복사하는 함수 맞으니깐 create와 set으로 대체하여 사용하시면 됩니다. 오류지적해주셔서 감사합니다.