ちょっと歩みが遅すぎて埒が明かなさそうなので問題に関する方針を変えてみることにします。

これまでは一問一問結構粘って、結果一日一問やったら終わりみたいな感じになってしまっていたので、ちょっとサクサク行くようにしてみます。Lisp のエラーとかそういうところでハマって時間を取られてしまったら答えあわせをしてしまって、写経しつつ自分のコードと比較をして理解をするようにします。

また、問題も一問で最大30分を目安にしてそれでもダメだったら諦めて答えを見ながら理解を進めるようにします。

Lisp 関連のエラーで悩まされて時間を潰すことがほとんどだったので、これで随分進みは良くなるんじゃないかな～?あと、ちょっと Gauche+Meadow の環境が辛いので別の環境を試したほうがいいのかも。 SICP コースだと Racket がお勧めっぽいので、そちらも試してみます。

問題回答

問1.24
gauche には random が無いようなので先人の知恵を拝借。
また、Gauche では true/false は #t/#f のようなのでこれは読み替えて使用。

回答からコードを持ってきて実行しても、素数のはずなのに素数ではないと判定されてしまう。何故～?

gosh> (fast-prime? 1000000000000037 10)
#f

仕方ないので解説を読む。

The timing numbers from the Fermat test start out looking pretty poor compared to what we've seen previously. This has mostly to do with the completely arbitrary number of random values I chose to test each prime with. As we increase the size of the numbers we're testing, you can see that the time using the Fermat test barely increases at all. We can verify that the time increase is logarithmic by observing that as the numbers under test increase by a factor of 10, the ratio column increases by a factor of roughly three. This logarithmic characteristic is due to the fact that the expmod procedure used in fermat-test has a logarithmic time complexity.

値が小さいときには非常に芳しくない結果となり、値が大きくなっても log10 ではなく log3 程度の効率化ししかなっていない。
これは、expmod が対数時間複雑性を持っているから、とのこと(P.29 の頭で説明されていた)。

問1.25
先人の知恵を拝借。

注釈 46 に解説があるのであわせて読む。

巨大な整数を扱うのはコストがかかるため、その影響が出てくるとのこと。なるほどー。

今日は方針を決めたりそれをメモしたりするのに時間をとられたのでここまで。よくわからないままウンウン悩むよりはサクサクと
答えを見ながら理解したほうがいい気はするので当分この流れでいってみる。