이 문제는 expmod 프로시저를 앞에서 썼던 fast-expt 프로시저로 간단하게 한다면

그 의미가 동일한지 묻는 질문입니다.

그래서 해당 소스를 바꾸었습니다.

예전 소스를 주석처리하고 새롭게 적었습니다.

저는 처음에 그 결과가 동일하지 않나 생각했습니다.

하지만 완전히 빗나갔습니다.

앞의 것이 예전 결과, 뒤의 것이 새로 변경한 결과입니다.

구한 값은 제대로 나왔지만 시간 차이가 어머어마합니다.

앞의 것은 시간 차가 0이 나올 정도로 빠르게 계산되었지만,

뒤의 것은 기다리다못해 제가 Stop 버튼을 눌렀습니다.

왜 이런 차이가 나는걸까요?

그 이유를 찾다가 문득 하나를 알았습니다.

'전자의 것은 마지막에 aⁿ을 return 하는 것이 아니라

계속 remainder한 값을 return하는구나.'

무슨 의미인지 이렇게 설명하겠습니다.

예를 들어 a = 3, n = 10이라 하겠습니다.

그럼 후자의 경우 fast-expt를 수행을 끝까지 마치면 3^10인 59049을 내놓습니다.

그런 다음 59049와 10의 나머지인 9를 return합니다.

하지만 전자의 경우 조금 다릅니다.

exp가 10 -> 5 -> 4 -> 2 -> 1 -> 0일 때 조건에 따라 실행되는 식을 적겠습니다.

exp = 10 : (remainder (square (expmod 3 (/ 10 2) 10)) 10)

exp = 5 : (remainder (* 3 (expmod 3 (- 5 1) 10)) 10)

exp = 4 : (remainder (square (expmod 3 (/ 4 2) 10)) 10)

exp = 2 : (remainder (square (expmod 3 (/ 2 2) 10)) 10)

exp = 1 : (remainder (* 3 (expmod 3 (- 1 1) 10)) 10)

exp = 0 : 1

여기서 각 식의 expmod 프로시저를 차례로 실행시키고 return값을 대체시킵니다.

따라서 0과 1 사이를 보면 다음과 같습니다.

(remainder (* 3 1) 10)

(remainder 3 10)

3

따라서 exp = 2의 식 속의 expmod 프로시저는 3이 됩니다.

(remainder (square 3) 10)

(remainder 9 10)

9

이를 계속 반복하겠습니다.

(remainder (square 9) 10)

(remainder 81 10)

1

(remainder (* 3 1) 10)

(remainder 3 10)

3

(remainder (square 3) 10)

(remainder 9 10)

9

따라서 마지막으로 나오는 값은 9로 위의 것과 동일합니다.

하지만 중간에 remainder가 계속 실행이 되어 return되는 값이 늘어나지 않습니다.

그렇기에 n이 클수록 속도 차이가 심하게 나는 것입니다.

이에 대한 설명을 밑에 주석으로 이런 글이 있습니다ㅏ.

'x, y, m이 어떤 정수라 할 때,

x × y modulo m은 x modulo m과 y modulo m의 나머지를 구한 다음에,

이를 곱한 값을 modulo m한 나머지와 같다.'라고 적혀있습니다.

(SICP 66쪽)

따라서 위와 같은 식으로 적은 것입니다.

이것을 보니 정말 대단하다는 생각이 듭니다.

수학적 원리를 저렇게 프로그램 언어로 표현했으니까요.

이를 문제로 접하지 않았다면 몰랐을 것입니다.

저도 저렇게 멋진 알고리즘을 짤 수 있을까요?

그 전에 저런 알고리즘을 이해부터 해야겠습니다.OTL....

이번에 배운 것은 하나.

recursive한 프로시저를 생각할 때 실행 후 돌아올 때

어떤 값으로 넘어와 남아있는 식과 어떤 조합을 이루는지 고려해야한다는 것입니다.

지금까지 대체로 파고드는 것만 신경썼고 돌아올 때는 값만 회수하였기에

이 문제를 제대로 풀지 못한 듯싶습니다.

좋은 문제 하나 접하였습니다.^^

참조

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

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

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