1.2.4~1.2.6
1.2.4 べき乗
べき乗を計算する手続きにおいて、各手続きのステップ数およびスペースの増加に関して4通りが紹介されている。
・線形再帰 ステップ・スペースともにO(n)
・線形反復的 ステップはO(n)、スペースはO(1)
・対数的再帰 ステップはO(log n)、スペースはO(n)
・対数的反復 ステップはO(log n)、スペースはO(1)
1.2.6 例:素数性のテスト
フェルマーテストはちょっとややこしいです。まとめると以下のようになります。
・nが素数 => フェルマーの小定理は成立する は常に真。
・フェルマーの小定理が成立しない => nは合成数 は常に真(上の対偶)。
・フェルマーの小定理が成立する => nは素数 はほとんど全てが真であるが、偽にもなる(カールマイケル数)
これらを用いて大きな数nが素数であるかを判定するには、nでフェルマーテストを行います。
expmodの計算はかなり紛らわしいです。
冪乗の剰余を計算するとありますが計算方法が特殊です。
実際には剰余の計算は1回ではなく、再帰のステップごとなので(n-1)回実行しています。
1回だけ剰余を計算する場合との違いは問題1.25を参照してください。
(expmod 10 4 3) (remainder (square (expmod 10 2 3) ) 3) (remainder (square (remainder (square (expmod 10 1 3) ) 3) ) 3) (remainder (square (remainder (square (remainder (* 10 (expmod 10 0 3) ) 3) ) 3) ) 3) (remainder (square (remainder (square (remainder (* 10 1) 3) ) 3) ) 3) (remainder (square (remainder (square (remainder 10 3) ) 3) ) 3) (remainder (square (remainder (square 1) 3) ) 3) (remainder (square (remainder 1 3) ) 3) (remainder (square 1) 3) (remainder 1 3) 1
文字列の表記
問題21で文字列の表記を扱います。
シングルクオーテーションで文字列の表記を、演算子newlineで空行を出力できます。
> 'string 'string > 'test 'test > newline #<procedure:newline> > (newline) > newline 'test #<procedure:newline> 'test > (newline) 'test 'test