상세 컨텐츠

본문 제목

BigFloat로 Pi를 구해보자-7. 나눗셈 최적화와 큰O 표기법(Big-O Notation)

프로그래밍/Multi precision

by ∫2tdt=t²+c 2012. 11. 1. 14:19

본문



전 연재에서 Newton-Raphson 방법으로 역수를 계산해보았는데요, Newton-Raphson 방법의 특징을 이용해서 코드를 조금더 최적화할 수 있습니다.

Newton-Raphson 방법은 수치 계산에 있어서 점진적(incremental)입니다. 무슨 말인가 하면, 반복적으로 같은 알고리즘을 적용하여 나가면서 수치 계산의 정밀도를 높여가는데, 중간에 계산을 멈추었다가도 그 중간결과를 이용해 다시 계산을 시작해 나가면 더 높은 정밀도를 얻을 수 있다는 것입니다.


Goldschmidt의 방법은 연속적으로을 곱해나가면서 역수를 계산해내었는데요, 이는 의 값을 따로 알고있어야만 다음 과정으로 넘어가서, 더 높은 정밀도의 결과를 얻을수 있지요. 즉 이 알고리즘은 incremental하지 않습니다.


incremental한 Newton-Raphson알고리즘은 어떤 정밀도로 계산된 결과이던간에, 한 단계 계산을 진행하면 항상 더 높은 정밀도의 결과를 얻을 수 있습니다. 이 말은 즉 소수점 이하 n자리 정밀도의 역수를 계산하기 위해서 처음부터 소수점 아래 n자리 실수를 가지고 계산할 필요 없이, 작은 자릿수로 시작해 그 자리수를 점차 늘려가도 된 다는 것이지요.



코드를 볼까요?


중간에 정밀도를 조절하는 코드가 추가되었습니다.

최적화 이전에 128 크기의 역수를 구한다고 했을때는

128 크기 실수끼리의 연산(덧셈, 곱셈)을 약 10번 해야했지만,

최적화 이후에는

차례로 4, 6, 9, 13, 19, 28, 42, 63, 94 ... 크기의 실수끼리의 연산을 하면되므로,

확실히 계산량이 줄어듭니다.


실제 계산속도는 다음과 같네요.

   최적화 이전
 최적화 이후

 시간(1024크기, 8회 반복)

 1704ms

 151ms

와우 10배 이상 빨라졌네요.



실제로 프로그램을 돌려보기 전에 알고리즘의 성능을 측정할수 있는 방법이 있으면 참 좋을텐데.. (일일히 코드 작성해서 테스트해보는것도 쉬운일이 아니니깐요)

그래서 전산학자들과 프로그래머들은 시간복잡도라는 개념을 사용합니다. 자세한 것을 위키백과를 참조.

알고리즘의 시간복잡도(얼마나 시간이 걸리는지)를 나타내기 위해 큰 O표기법을 흔히 사용하는데, 이는 쉽게 설명하면 최악의 경우 걸리는 시간을 나타내는 것이지요.


만약 어떤 알고리즘이 O(log n)의 시간 복잡도를 가진다면, 크기 n이 커짐에 따라 실행시간은 최악의 경우 log n에 비례하여 커진다는 뜻입니다. 각각의 알고리즘의 시간복잡도를 계산해봄으로써 간단하게 어떤 알고리즘이 대략 어느 정도 빠른지 가늠할 수 있지요.


먼저 덧셈 연산입니다.

우리가 구현했던 덧셈연산은 크기가 n인 두 정수를 더한다고 했을때, 최대 n번의 덧셈, n번의 비교연산, 최악의 경우 n번의 받아올림이 이루어집니다. 각각의 연산이 유사한 시간이 걸려 처리된다고 가정하면 크기 n인 정수를 더하는데에는 최악의 경우 3n번의 연산이 필요합니다. 그러므로 우리의 덧셈 연산은 O(n)의 시간복잡도를 가진다고 할수 있습니다.[각주:1]


마찬가지 방법으로 뺄셈연산도 O(n)의 시간복잡도를 가집니다.


우리가 구현했던 곱셈 연산의 경우 크기가 n인 두 정수를 곱하기 위해서는 최대 n2번의 곱셈과 덧셈이 필요합니다. 그러므로 곱셈 연산의 시간복잡도는 O(n2)이 됩니다.


그러면 Newton-Raphson 방법으로 구현한 나눗셈 연산의 시간복잡도를 계산해볼까요?


a. 최적화 이전

while문 안에는 mulsub 연산( O(n2) )이 하나 있고, mul연산( O(n2) )이 하나 있고, add연산( O(n) )이 하나 있네요. while문 밖에 있는 것들은 크기 n에 따라 연산량이 변하지 않으므로 생략할께요. while문은 정밀도가 매번 2배씩 증가한다는 Newton-Raphson 방법의 특징상 약 log n번 반복됩니다.

그러므로 전체 연산은 최악의 경우 log n * (n2 + n2 + n) 회 연산이 수행될 것입니다. 즉 시간복잡도는 O(n2 log n)이 될 것입니다.


b. 최적화 이후

while문의 반복횟수는 변화가 없을 겁니다. 매 반복마다 연산하는 크기가 p배씩 증가한다고 하면, 처음에는 p2 회의 연산, 두 번째는 p4회의 연산, 세 번째는 p6회의 연산... 을 하게 될것입니다. 전체 반복회수를 log n이라고 하면, 총 연산횟수는 등비수열 합 공식에 의해

가 될 것입니다. lop p = 1이 되도록하는 적당한 p를 설정한다면, 시간복잡도는 O(n2)이 될 수 있습니다.


두 알고리즘은 약 log n 배만큼 연산량이 차이가 납니다. 크기가 1024였던걸 감안하면 최적화 이후 속도가 10배가량 증가한 결과[각주:2]와 얼추 맞아떨어지네요.

  1. 3n번에 비례하는것은 n번과도 비례하므로, O(n)이라고 표기합니다. 점근표기법에서는 계수가 중요한 의미를 지니지 않습니다. [본문으로]
  2. 계산이론에서 다루는 log는 주로 밑이 2인 로그입니다. 그러므로 log 1024는 10이겠지요 [본문으로]

관련글 더보기

댓글 영역