search

sicp-reading / sicp-source

source 管理用のリポジトリ
0 stars 0 forks source link

Seems the implementation of expmod wrong #12

Closed cocoatomo closed 10 years ago

cocoatomo commented 10 years ago

https://github.com/sicp-reading/sicp-source/blob/master/source/answers/chapter_1/ex1.24.scm#L16 の箇所の square の適用位置がおかしいので, 計算量が log(N) になっていないように見える.

cocoatomo commented 10 years ago

こちらの実装を想定していたのですが, 計算量を求めてみたら iriya-ufo さんのものと変わりませんでした. クローズします.

(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (expmod (remainder (square base) m) (/ exp 2) m))
        (else
         (remainder (* base (expmod base (- exp 1) m))
                    m))))