計算機科学のブログ

Building Abstractions with Functions - Formulating Abstractions with Higher-Order Functions - Functions as Returned Values - strategy, iterative improvement, fixed point, square root

Structure and Interpretation of Computer Programs: JavaScript Edition(Harold Abelson(著)、Gerald Jay Sussman(著)、Julie Sussman(著)、The MIT Press)のChapter 1(Building Abstractions with Functions)、1.3(Formulating Abstractions with Higher-Order Functions)、1.3.4(Functions as Returned Values)、Exercise 1.46の解答を求めてみる。

コード

function iterative_improve(is_good_enough, improve) {
    function iter(guess) {
        return is_good_enough(guess) ?
            guess :
            iter(improve(guess));
    }
    return iter;
}
function square(x) {
    return x * x;
}
function average(x, y) {
    return (x + y) / 2;
}
function sqrt(x) {
    return iterative_improve(
        guess => Math.abs(square(guess) - x) < 0.00001,
        guess => average(guess, x / guess)
    )(x);
}

console.log(`√2 = ${sqrt(2)}`);
console.log(`√3 = ${sqrt(3)}`);
console.log(`√4 = ${sqrt(4)}`);
console.log(`√100 = ${sqrt(100)}`);

const tolerance = 0.00001;
function fixed_point(f, first_guess) {
    return iterative_improve(
        guess => Math.abs(f(guess) - guess) < tolerance,
        f
    )(first_guess);
}

console.log(fixed_point(y => Math.sin(y) + Math.cos(y), 1));

function sqrt_fixed_point(x) {
    return fixed_point(y => average(y, x / y), 1);
}
console.log(`√2 = ${sqrt_fixed_point(2)}`);
console.log(`√3 = ${sqrt_fixed_point(3)}`);
console.log(`√4 = ${sqrt_fixed_point(4)}`);
console.log(`√100 = ${sqrt_fixed_point(100)}`);

入出力結果(Terminal, Zsh)

% node answer1.46.js
√2 = 1.4142156862745097
√3 = 1.7320508100147274
√4 = 2.0000000929222947
√100 = 10.000000000139897
1.2587228743052672
√2 = 1.4142156862745097
√3 = 1.7320508100147274
√4 = 2.0000000929222947
√100 = 10.000000000139897
%