そもそも、 (* (expmod base (/ exp 2) m) (expmod base (/ exp 2) m)) なんてことをやると、ここで計算が二系統に分かれる。しかも同じ計算を倍々にし続けることになる。 これはめちゃくちゃスペースをくう。整数の平方を求めるのに比べて大きく遅くなる。 …

とりあえずは、ここに書いてありますexpmodを実装してみる。 1 #!/usr/local/bin/gosh 2 ;; -*- coding: utf-8 -*- 3 4 (use ggc.debug.trace) 5 (use math.mt-random) 6 7 ;;random;;;;;;;;;;;;;;;;;;;;;; 8 (define mt (make <mersenne-twister> :seed (sys-time))) 9 (defin</mersenne-twister>…

Fermat法を利用してのprime-test ちゃんと、θ(log n)な感じの計算量増加。 底を10とすると、nが100倍されても、計算量が2倍ってやつ。 nが1000倍なら計算量は3倍。いけてます。 goucheだからかわかんないけど、教科書のFermat法の実装を使うだけだとエラーが…