猫型エンジニアのブログ

プログラム/ネットワーク系の技術関連をまとめたページです 

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.5 最大公約数

ユークリッドアルゴリズムの紹介

(define (gcd a b)
  (if (= b 0)
      a
      (gcd b (remainder a b))))

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