n^m
課題は単純にnを2m回掛け合わせるのではなく
と書いてありますが、寧ろ単純にかけるだけの関数を作って一度練習してみるといいでしょう。
(define (^ n m)
(if (zero? m)
1
(* n (^ n (- m 1)))
))
見ての通り、nをm回かけるだけの関数です。例えば、(^ 2 32)ならば32回も2をかけるだけです。これ、効率が悪いと思いませんか?
n^2^m
(^ 2 32)のように、指数mが2のべき乗の形をしている場合は、例えば(^ (^ 2 16) 2)と変えるだけで一気にかける回数を半分近く減らすことができます。数学的には2^32も(2^16)^2も等価ですが、かける回数でみると計算量はまったく違うことがわかると思います。
そこで次はn^2^mを計算する関数を作ってみましょう。ここで重要なのは、n^2^m=(n^2^m-1)^2であることです。
(define (^ n m)
(if (zero? m)
1
(* n (^ n (- m 1)))
))
(define (^2^ n m)
(if (zero? m)
n
(^ (^2^ n (- m 1)) 2)
))
このように、たとえ2^1024でも1000回も再帰する必要はなく、実質的に10回の再帰だけで済ませられることが分かります(※1024は2の10乗)。文字通り、計算量のオーダーが違うというわけです。
n^2m
もう気付いていると思いますが、一般のn^mの場合でも、同じような手法で掛ける回数を減らせますね。つまり、mが偶数ならば(n^m/2)^2、mが奇数ならばn*(n^(m-1)/2)^2という風に、指数の偶奇で場合分けして指数部分を分解していけばいいのです。
課題では指数が偶数のべき乗を求める関数pow(n,m)=n^2mを作ればいいわけです。つまり、mが偶数ならば(pow(n,m/2))^2、mが奇数ならば(n*pow(n,(m-1)/2)^2と定義することで、powをpow
自身で再帰定義できます。mは正整数なので、再帰終了条件はpow(n,1)=n*nとするのがいいでしょう。
ここで、偶数・奇数の判定にmodulo
が使え、m/2及び(m-1)/2を求めるのにはquotient
が使えます。(modulo n m)はnをmで割った余りを求め、(quotient n m)はnをmで割った商[n/m](※整数値)を求めます。