Euclidのアルゴリズム最大公約数について。２つの整数 a, b の最大公約数を求める場合、普通は両方の数を素因数分解して、 共通因子を取り出して乗算するけど、もっと効率のいい、すげーアルゴリズムがあるみたい。このアルゴリズムは、 「a を b で割った剰…

これ結構楽しかった。 【問題】 Fibonacci数を対数的ステップ数で計算するうまいアルゴリズムがある。 1.2.2節の fib-iter プロセスで使った状態変数 a, b の変換、 a ← a + b b ← aに注意しよう。この変換を T と呼ぶ。 1 と 0 から始め、T を繰り返して n …

あ。。 【問題】 問題 1.16, 1.17 の結果を使い、加算、二倍、二分による、対数的ステップ数の、 ２つの整数の乗算の反復的プロセスを生成する手続きを工夫せよ。 【解答】 これ、1.17の段階でやっちゃってるので省略。

割とすんなりできたなぁ。 【問題】 本節のべき乗アルゴリズムは乗算の繰り返しによるべき乗の実行に基づいていた。 同様に整数の乗算を加算の繰り返しで実行できる。 次の乗算手続きは expt 手続きに似たものである。 （この言語には加算はあるが乗算はない…