/** * SICP練習1.16〜1.18 */ import std.stdio; /** * 練習1.16。 * 反復で b の n 冪乗を求める。 * 時間コストは log(n) でなければ成らない。 */ int fastExpt(int b, int n) { int a = 1; a = iter(b, n, a); return a; } int iter(int b, int n, int a) { writefln("b = %d, n = %d, a = %d", b, n, a); if (n == 0) { return a; } else if (n % 2 == 0) { return iter(b * b, n / 2, a); } else { return iter(b, n - 1, a * b); } } /** * 練習1.17。 * 「足す、倍、半分」を用いて「積」を求める。 * 時間コストは log(n) でなければ成らない。 */ int fastMulti(int b, int n) { if (n == 0) { return 0; } else if (n == 1) { return b; } else { if (n % 2 == 0) { return fastMulti(doulbe(b), halve(n)); } else { return b + fastMulti(b, n - 1); } } } /** * 練習1.18。 * 「足す、倍、半分」を用いて、反復法で「積」を求める。 * 時間コストは log(n) でなければ成らない。 */ int fastMulti2(int b, int n) { int a = 0; a = iter2(b, n, a); return a; } int iter2(int b, int n, int a) { writefln("b = %d, n = %d, a = %d", b, n, a); if (n == 0) { return a; } else if (n % 2 == 0) { return iter2(doulbe(b), halve(n), a); } else { return iter2(b, n - 1, a + b); } } int doulbe(int a) { return a + a; } int halve(int a) { // a は偶数とする return a / 2; } void main() { // for 1.16 int b = 2; int n = 10; writefln("\n---- 1.16 ----"); int ret = fastExpt(b, n); writefln("\nfastExpt(%d, %d) = %d", b, n, ret); // for 1.17 ret = fastMulti(b, n); writefln("\n---- 1.17 ----"); writefln("fastMulti(%d, %d) = %d", b, n, ret); // for 1.18 writefln("\n---- 1.18 ----"); ret = fastMulti2(b, n); writefln("\nfastMulti2(%d, %d) = %d", b, n, ret); }