引き続き整数計算の世界。 ノート 最大公約数。第２章で有理数（分数で表せる数）の計算を実装する事になるが、約分の際にGCDが計算出来る必要がある。 ユークリッドの互除法 aをbで割った時の余りをrとした時、aとbの最大公約数はbとrの最大公約数に等しい…

ノート 冪乗。 b8を計算するのにb×b×b×b×b×b×b×bと計算するより、b2=b×b、b4=b2×b2、b8=b4×b4とした方が効率的。 nが偶数の時、bn=(bn/2)2、 nが奇数の時、bn=b×bn-1 とするとかけ算の回数を減らせる。 Exercise 1.16 bnを求める。 iterative procedureの引…

ノート 成長の次数。あるいは計算量の成長度合い。 入力の大きさとしては引数の値そのものだったり計算の精度だったり。計算量の尺度も計算のステップ数だったり必要なメモリサイズだったり。 と表現する。良く見かけるO記法とは実は少し違うらしい。 Θ記法…

3ヶ月ぶりの更新と書いたのが8月25日。それから4ヶ月。少しずつ読み進めて入るのですがまたまた久しぶりのアップデートとなりました。手続き呼び出しが実行されて行く様子の勉強の続きです。 ノート 計算過程が木構造になる例。数学的定義をそのままプログラ…