1.2.4 べき乗

文責:@naoiwata

べき乗計算におけるプロセスを考える.

線形再帰的プロセスのべき乗計算

\(b^n = b * b^{n-1}\)

\(b^0 = 1\)

から以下の手続きに翻訳できる.

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

ステップ数は \(\Theta(n)\), スペースは \(\Theta(n)\) を要する.

線形反復的プロセスのべき乗計算

(define (expt b n)
  (expt-iter b n 1))

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

ステップ数は \(\Theta(n)\), スペースは \(\Theta(1)\) を要する.

逐次平方を使ったべき乗計算

\(b^n = (b^{n/2})^2\) (n が偶数)

\(b^n = b * b^{n-1}\) (n が奇数)

上の定義を用いて逐次平行を利用すると以下の手続きに翻訳できる.

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

ステップ数は \(\Theta(\log n)\), スペースは \(\Theta(\log n)\) を要する.(log は 2 を底とする)

逐次平方を使うことでより少ないステップでの計算が可能になる.