불변식은 지수를 안전하게 줄이게 한다.
빠른 거듭제곱은 지수가 짝수일 때 밑을 제곱하고 지수를 반으로 줄이며 홀수 단계에서 남는 인수는 명시적인 곱에 옮겨 둡니다.
생각해 볼 질문
계산하는 거듭제곱을 바꾸지 않으면서 지수를 어떻게 빠르게 줄일까요?
- 밑과 지수와 곱을 프로세스의 완전한 상태로 추적하기
- 짝수 지수에서 밑을 제곱하고 지수를 반으로 줄이기
- 홀수 단계에서 밑 인수 하나를 곱으로 옮기기
- 곱과 밑의 지수승을 곱한 값을 불변식으로 유지하기
모든 호출에서 product × base^exponent는 처음 요청한 거듭제곱과 같습니다. exponent가 짝수이면 base를 제곱하고 exponent를 반으로 줄여도 이 값이 유지됩니다. exponent가 홀수이면 product에 base를 곱하고 exponent에서 1을 빼도 같은 값이 유지됩니다.
exponent가 0이 되면 남은 거듭제곱은 1이고 product에 답이 모두 들어 있으므로 프로세스가 멈춥니다. 이력 프로그램은 모든 호출의 전체 상태를 기록해 짝수 전이와 홀수 전이를 직접 확인하게 합니다.
(begin
(define (fast-expt base exponent product)
(cond ((= exponent 0) product)
((even? exponent)
(fast-expt (* base base)
(/ exponent 2)
product))
(else
(fast-expt base
(- exponent 1)
(* product base)))))
(fast-expt 3 13 1))리스펙스 학습용 런타임리스펙스 SICP 프로필 1.0.0
리스펙스 SICP 런타임 불러오는 중
리스펙스 · SICP 코드UTF-8 363 / 1,048,576바이트
예제
결과—
- 출력
- —
- 값
- —
- 진단
- —
보이는 실행 흐름0 / 0 개의 실행 이벤트
첫 프로그램은 1594323을 반환합니다. 두 번째 프로그램은 ((2 10 1) (4 5 1) (4 4 4) (16 2 4) (256 1 4) (256 0 1024))를 반환합니다.
각 전이 전에 even? 판단을 따라가세요. 짝수 단계에서는 base가 제곱되고 exponent가 반으로 줄며 홀수 단계에서는 product가 base를 받아들이고 exponent가 1만큼 줄어듭니다. 기록된 상태는 이 정확한 정수 입력만 설명하며 리스펙스 바우치나 권한이 아닙니다.
힌트를 보기 전에 프로그램을 바꿔 보세요.
fast-expt로 5의 11제곱을 계산하세요. 실행하기 전에 지수가 줄어드는 각 단계가 홀수인지 짝수인지 적어 보세요.
힌트 하나 보기
홀수 단계는 1을 빼서 다음 지수를 짝수로 만듭니다. 짝수 단계는 지수를 반으로 줄입니다.