[ 目次, 前節, 次節, 索引 ]

1.2.4 べき乗

ある数のべき乗を計算する問題を考えよう. 引数として底bと正の整数の指数nをとり, bnを計算する手続きにしたい. 一つの方法は再帰的定義

bn = b ・ bn - 1
b0 = 1

を使うことで手続きにすぐ翻訳出来る. 

(define (expt b n)
  (if (= n 0)
      1
      (* b (expt b (- n 1)))))
これは線形再帰的プロセスで, Θ(n)ステップとΘ(n)スペースを必要とする. 階乗と同様に, 等価な線形反復が作れる: 

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

(define (expt-iter b counter product)
  (if (= counter 0)
      product
      (expt-iter b
                (- counter 1)
                (* b product))))
これはΘ(n)ステップとΘ(1)スペースを必要とする.

   逐次平方を使えばより少ないステップでべき乗が計算出来る. 例えばb8の計算は

b・(b・(b・(b・(b・(b・(b・b)))))))

とするよりは乗算三回で

b2 = b・ b

b4 = b2・ b2

b8 = b4・ b4

と計算する.

   これは2のべき乗の指数の時, うまくいく. 一般の場合でも,

bn = (bn/2)2        nが偶数の時

bn = b・bn-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))))))
整数が偶数かどうかをテストする述語は基本手続き remainderを使って定義出来る. 

(define (even? n)
  (= (remainder n 2) 0))
fast-exptから作られるプロセスは, スペースもステップ数もnに対数的に増加する. これを見るにはfast-exptを使ったb2nの計算はbnの計算より乗算をもう一回しか必要としないことを知ればよい. 新しい乗算が使える度に計算出来る指数の大きさは(近似的に)二倍になる. そこで, 指数nに対して必要な乗算の数は2を底とするnの対数の程度に増加する. プロセスはΘ(log n)の増加である.37

   Θ(log n)とΘ(n)の増加の差は, nが大きくなると際だつ. 例えばn = 1000でfast-exptは14回の乗算しか必要としない.38 逐次平方の考えで, 対数的ステップ数でべき乗を計算する反復的アルゴリズムも作れる(問題1.16参照). だが, 反復的アルゴリズムによくあることだが, 再帰的アルゴリズムのように直截的には書くことが出来ない.39

問題 1.16

fast-exptのように, 逐次平方を使い, 対数的ステップ数の反復的べき乗プロセスを生成する手続きを設計せよ. (ヒント: (bn/2)2 = (b2)n/2に注意し, 指数nと底bの他にもう一つの状態変数aを用意する. 状態の移変りで積abnが不変であるように状態遷移を定義する. プロセス開始時にaを1とし, プロセス終了時にaが結果になるようにする. 一般に, 状態の移変りに不変のままの 不変量 (invariant quantity)を定義する技法は, 反復的アルゴリズムの設計に有用である.)

問題 1.17

本節のべき乗アルゴリズムは, 乗算の繰返しによるべき乗の実行に基づいていた. 同様に整数の乗算を加算の繰返しで実行出来る. 次の乗算手続きは(この言語には加算はあるが, 乗算はないと仮定する)expt手続きに似たものである: 

(define (* a b)
  (if (= b 0)
      0
      (+ a (* a (- b 1)))))
このアルゴリズムはbに線形のステップ数をとる. 加算の他に整数を二倍するdouble演算と(偶数の)整数を2で割るhalve演算もあるとしよう. これらを使い, fast-exptと類似の対数的ステップ数の乗算手続きを設計せよ.

問題 1.18

問題1.16, 1.17の結果を使い, 加算, 二倍, 二分による, 対数的ステップ数の, 二つの整数の乗算の反復的プロセスを生成する手続きを工夫せよ.40

問題 1.19

Fibonacci数を対数的ステップ数で計算するうまいアルゴリズムがある. 1.2.2 節のfib-iterプロセスで使った状態変数aとbの変換: a ← a + bとb ← aに注意しよう. この変換をTと呼ぶ. 1と0から始め, Tを繰り返してn回作用させると, Fib(n + 1)とFib(n)の対が出来る. いいかえれば, Fibonacci数は対(1, 0)にTn, つまり変換Tのn乗を作用させると得られる. さて, Tpqは対(a, b)をa ← bq + aq + apとb ← bp + aqに従って変換するものとし, Tを変換族Tpqのp = 0とq = 1の特例としよう. 変換Tpqを二回使うとその効果は同じ形式の変換Tp'q'を一回使ったのと同じになることを示し, p'とq'をp, qを使って表せ. これで変換を二乗する方法が得られ, fast-exptのように逐次平方を使い, Tnを計算することが出来る. これらをすべてまとめ, 対数的ステップ数の以下の手続きを完成せよ.41 
(define (fib n)
  (fib-iter 1 0 0 1 n))

(define (fib-iter a b p q count)
  (cond ((= count 0) b)
        ((even? count)
         (fib-iter a
                   b
                   ⟨??⟩      ; p'を計算
                   ⟨??⟩      ; q'を計算
                   (/ count 2)))
        (else (fib-iter (+ (* b q) (* a q) (* a p))
                        (+ (* b p) (* a q))
                        p
                        q
                        (- count 1)))))



37 より正確には, 必要な乗算の数は2を底とするnの対数に, nの2進表現での1の数を足して1を引いたものに等しい. 合計は2を底とするnの対数の二倍より常に小さい. 増加の程度の定義にあった定数k1とk2は任意であるから, 対数的プロセスの場合, 対数の底は関係せず, これらのプロセスはΘ(log n)と書く.

38 1000乗など誰も気にしないと思うかも知れない. 1.2.6節参照.

39 この反復的アルゴリズムは古く, Áchárya Pingalaが200 B.C.以前に書いた Chandah-sutraに現れる. べき乗のこの方法や他の方法の議論と解析はKnuth 1981の4.6.3節を参照のこと.

40 「ロシア農民の方法」として知られているこの乗算アルゴリズムは古い. 使用例は1700 B.C. 頃, エジプト人 A'h-moseの書いた(それも更に古い文献から写した), 現存する数学の最も古い二つの文献の一つ, Rhindパピルスで見つかった.

41 この問題は Kaldewaij 1990の例から, Joe Stoyが提案した.

[ 目次, 前節, 次節, 索引 ]