第一章　練習1.15　正弦関数を求める

問題規模が大きくなる時、コストの増加は線形、指数、対数などの形となります。

SICPの練習 1.15 です。x は十分に小さい時、sin(x) = x は近似成立。また、sin(x) = 3 * sin(x / 3) - 4 * sin(x / 3)³ は常に成り立ちます。上記ルールに基づいて sin(a) を求めて下さい。また、その時の空間と時間コストは何でしょう？

/**
* sin(x) の計算
*/
import std.stdio;
import std.math;
int loop;
float SMALL_ENOUGH = 0.1;
float sine(float x) {
if (abs(x) <= SMALL_ENOUGH) {
return x;
}
return p(sine(x / 3.0));
}
float cube(float x) {
return x * x * x;
}
float p(float x) {
loop++;
return 3 * x - 4 * cube(x);
}
void main() {
loop = 0;
float x = 1.215;
float ret = sine(x);
writefln("sine(%f) = %f, loop = %d", x, ret, loop);
loop = 0;
x = 12.15;
ret = sine(x);
writefln("sine(%f) = %f, loop = %d", x, ret, loop);
loop = 0;
x = 121.5;
ret = sine(x);
writefln("sine(%f) = %f, loop = %d", x, ret, loop);
loop = 0;
x = 1215;
ret = sine(x);
writefln("sine(%f) = %f, loop = %d", x, ret, loop);
loop = 0;
x = 12150;
ret = sine(x);
writefln("sine(%f) = %f, loop = %d", x, ret, loop);
loop = 0;
x = 121500;
ret = sine(x);
writefln("sine(%f) = %f, loop = %d", x, ret, loop);
}

/** * sin(x) の計算 */ import std.stdio; import std.math; int loop; float SMALL_ENOUGH = 0.1; float sine(float x) { if (abs(x) <= SMALL_ENOUGH) { return x; } return p(sine(x / 3.0)); } float cube(float x) { return x * x * x; } float p(float x) { loop++; return 3 * x - 4 * cube(x); } void main() { loop = 0; float x = 1.215; float ret = sine(x); writefln("sine(%f) = %f, loop = %d", x, ret, loop); loop = 0; x = 12.15; ret = sine(x); writefln("sine(%f) = %f, loop = %d", x, ret, loop); loop = 0; x = 121.5; ret = sine(x); writefln("sine(%f) = %f, loop = %d", x, ret, loop); loop = 0; x = 1215; ret = sine(x); writefln("sine(%f) = %f, loop = %d", x, ret, loop); loop = 0; x = 12150; ret = sine(x); writefln("sine(%f) = %f, loop = %d", x, ret, loop); loop = 0; x = 121500; ret = sine(x); writefln("sine(%f) = %f, loop = %d", x, ret, loop); }

空間コストは O(1) でしょう。時間コストは log₃₍a) でしょう。