멱, 빠른 멱 연산

주어진 수에 대해 곱셈을 계산하다.이 과정의 매개 변수는 기수 b와 정정수의 지수 n이고 과정은 b^n을 계산한다.한 가지 방법은 다음과 같은 귀속 정의를 통해

b ^ n = b * b ^ (n - 1)
b ^ 0 = 1

선형 귀속: 【시간 복잡도: O(n), 공간 복잡도: O(n)】

(define (expt b n)
  (if (= n 0) 1
      (* b (expt b (- n 1)))))

선형 교체: 【시간 복잡도: O(n), 공간 복잡도: O(1)】

(define (expt b n)
  (define (expt-iter n product)
    (if (= n 0) product
        (expt-iter (- n 1) (* product b))))

  (expt-iter n 1))

빠른 멱 연산을 우리는 연속적으로 제곱을 구하여 더 적은 절차로 곱셈 연산을 완성할 수 있다.예를 들어 이런 방식으로 b^8을 계산하지 않는다.

b * (b * (b * (b * (b * (b * (b * b)))))) 

세 번의 곱셈으로 그것을 계산해 낸다.

b ^ 2 = b * b
b ^ 4 = b ^ 2 * b ^ 2
b ^ 8 = b ^ 4 * b ^ 4

만약 아래의 규칙을 채택한다면 우리는 연속적으로 제곱을 구하여 일반적인 곱셈 연산을 완성할 수 있다.

b ^ n = (b ^ (n / 2)) ^ 2      n 
b ^ n = b * b ^ (n - 1)        n 

귀속 알고리즘: 【시간 복잡도: O(logn), 공간 복잡도: O(logn)】

(define (fast-expt b n)
  (define (even?) (= (remainder n 2) 0))
  (define (square x) (* x x))

  (cond ((= n 0) 1)
        ((even?) (square (fast-expt b (/ n 2))))
        (else (* b (fast-expt b (- n 1))))))

반복 알고리즘: [관계 이용(b ^ (n / 2)) ^ 2 = (b ^ 2) ^ (n / 2) 또 하나의 추가 상태 변수ret를 유지하고 상태 변환을 정의하여 한 상태에서 다른 상태로 전환할 때 곱셈 a*(b^n)를 변하지 않게 한다. 중요한 사상: 불변량을 정의하여 상태 사이에서 변하지 않도록 요구한다] [시간 복잡도: O(logn), 공간 복잡도: O(1)]

(define (even? x) (= (remainder x 2) 0))    // racket ， 
(define (square x) (* x x))

(define (fast-expt b n)
  (define (fei b n ret)
    (cond ((= n 0) ret)
          ((even? n) (fei (square b)
                          (/ n 2)
                          ret))
          (else (fei b
                     (- n 1)
                     (* ret b)))))

  (fei b n 1))

//  
(fast-expt 2 4)
(fast-expt 3 3)
(fast-expt 4 5)
(fast-expt 5 3)
//  
16
27
1024
125

반복적으로 덧셈을 하는 방식으로 곱셈을 구하고 대수 (O (logn)) 의 계산 걸음수만 사용한다.

a * b = (a * (b / 2)) * 2
a * b = a + a * (b - 1)

【원리는 빠른 멱 연산 곱셈 멱과 유사하다.】
차례로 돌아가다

(define (double x) (* x 2))
(define (halve x) (/ x 2))

(define (multi a b)
  (cond ((= b 0) 0)
        ((even? b) (double (multi a
                                  (halve b))))
        (else (+ a
                 (multi a (- b 1))))))

교체하다

(define (double x) (* x 2))
(define (halve x) (/ x 2))

(define (mul a b)
  (define (mul-iter a b ret)
    (cond ((= b 0) ret)
          ((even? b) (mul-iter (double a)
                               (halve b)
                               ret))
          (else (+ a
                   (mul-iter a
                             (- b 1)
                             (* a ret))))))

  (mul-iter a b 0))

------------------------------------
// else  ：
(else (mul-iter a
                (- b 1)
                (+ a ret)))

//  
(mul 2 4)
(mul 5 20)
(mul 33 88)
(mul 99 11)
//  
8
100
2904
1089