이 문제는 피보나치 수열을 구할 때 계산 단계(order of growth)가 로그 차수가 되는

책의 말을 빌리면 똑똑한 알고리즘을 소개하고 있습니다.

변수 a, b를 'a <- a + b,  b <- a'로 하는 규칙을 T라 하고

T를 n번 수행하면 Fib(n + 1)과 Fib(n)을 구할 수 있습니다.

이를 확장해서 T_{pq}는 다음과 같은 규칙을 가진다면,

p = 0, q = 1일 때 위의 T와 같은 규칙이 됩니다.

'a <- bq + aq + ap,  b <- bp + aq'

여기서 T_{pq}를 두 번 수행한 결과가 T_{p'q'}을 한 번 수행한 것과 같도록

p', q'을 p, q에 관한 식으로 구하는 것이 문제입니다.

항등식에서 미지의 계수를 구하는 방법에

항등식 양변의 같은 차수의 항의 계수는 같다는 계수비교법이 있으니

a, b를 변수라 두고 p', q'을 미지의 계수라 하면 답이 나옵니다.

(이 말이 더 복잡한가요.;;)

그렇게해서 구해진 답은

p' = p² + q²,  q' = q² + 2pq입니다.

문제 밑에 소스가 적혀있습니다.

여기에 p'과 q'을 넣을 공간이 비워져있습니다.

위에서 구한 답을 해당 빈칸에 넣은 다음 실행시켰습니다.

fib 10까지 살펴보니 제대로 작동하고 있습니다.

그 뒤에 n을 100과 100,000을 만들어 돌렸습니다.

100,000의 경우 8초 정도 기다리니 답이 나왔습니다.

그 답의 양이 매우 길어 한 화면에 나오지 않는군요.

스크롤의 크기를 보시면 답의 길이를 짐작하실 수 있습니다.

숫자 개수를 살펴보니 총 20,899자리입니다.;;;;

유효숫자를 4개만 잡는다면 2.597 * 10^20898이네요.

10을 20,898번 곱한다라...;;;;;

이 거대한 숫자가 10초도 지나지 않아 나오다니 대단합니다.^^

정의에 맞게 작성한 경우 100을 구하려면 3분이 넘어도 답이 나오지 않습니다.

(결국 제가 break를 걸었습니다.)

이것이 Θ(log n)과 Θ(2ⁿ)의 차이인 듯싶습니다.

이래서 좋은 알고리즘을 써야하는군요.^^

낭만고양이님께서도 해당 문제에 대한 글을 적어주셨습니다.

'SICP Exercise : 연습문제 1.19'

낭만고양이님 말씀처럼 이건 수학 문제인 듯싶습니다.^^;;;

하지만 상당히 강력한 알고리즘을 구경할 수 있었기에 재미있었습니다.^^

이런 수학문제라면 환영합니다.(단, 이해하고 풀 수 있다면...OTL.....)

참조

Structure and Interpretation of Computer Programs 2/E - Page 61

실력 공통수학의 정석 - Page 90

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.