xのn乗の計算をしたい

Question

##xのn乗の計算をしたい

xのn乗を計算するプログラムを、letを用いて書きたいです。
試行錯誤して、エラーが出ないようにはなりましたが、実行に非常に時間がかかり、挙句「メモリを使い切りました」という表示が出てしまって計算できません。
プログラムを修正するべきなのだと思うのですが、初心者のため修正点が分かりません。
問題を指摘して頂けると嬉しいです。
Macbook airでDr.Racketを使用しています。

##記述したプログラム

(define (pow2 x n)
  (let ((y (pow2 x (/ n 2))))
    (cond ((= n 0) 1)
          ((= (modulo n 2) 0) (* y y))
          (else (* x y y)))))

Answer 1

コードを見る限り整数乗に限定した話だと思うのでその前提で話をします

まず「メモリを使い切りました」となる原因は関数の最初に再帰呼び出しをしてるところです。これが無限ループになっています。
少なくとも(= n 0)ではないことを確認してから再帰呼び出しするようにしてください。

それからschemeの割り算はほかの大半の言語が使ってるようなのような小数点以下切り捨てのものではないので、そこに注意しないとやっぱり無限ループになります。

Comments

[退会済みユーザー]

ご意見を参考に、letより先に(= n 0)の場合を記述し、/ではなくquotientを使用したところ上手くいきました。
教えて頂きありがとうございました。

Answer 2

Schemeについては分からないので方向だけ。

実はべき乗というのは、マイナス値や少数というのもあるんですね。
べき乗計算は遅い
それで調べてみると、テイラー展開を使って計算する、というような話が出てきます。
logとpowの計算

ただ、テイラー展開とか大学で習う内容なようなので・・・まぁ、分からなかったら手順だけ真似るのがいいかもしれません。

Comments

[退会済みユーザー]

参考になりました。
ありがとうございました。