計算機科学のブログ

Building Abstractions with Functions - The Elements of Programming - Example: Square Roots by Newton's Method - difference, ratio

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.1(The Elements of Programming)、1.1.7(Example: Square Roots by Newton’s Method)、Exercise 1.7の解答を求めてみる。

0.001未満で終了だと、小さい数字の場合は精度が低くなったり、大きい数字の場合は十分な精度でも計算を続けることになったり、あるいは循環して0.001未満にならずに計算が終了しない場合がある。

差じゃなくて比に変更してみる。

コード

let abs = Math.abs;

function square(x) {
    return x * x;
}
function improve(guess, x) {
    return average(guess, x / guess);
}
function average(x, y) {
    return (x + y) / 2;
}
function is_good_enough(previous_guess, guess) {
    return abs(1 - guess / previous_guess) < 0.001;
}

function sqrt_iter(previous_guess, guess, x) {
    return is_good_enough(previous_guess, guess) ?
        guess :
        sqrt_iter(guess, improve(guess, x), x);
}
function sqrt(x) {
    return sqrt_iter(2 * x, x, x);
}

for (const x of [4, 9, 2, 1e10, 1e-10]) {
    console.log(`√${x} ≈ ${sqrt(x)}`);
}

入出力結果(Terminal, Zsh)

% node answer1.7.js 
√4 ≈ 2.0000000929222947
√9 ≈ 3.000000001396984
√2 ≈ 1.4142135623746899
√10000000000 ≈ 100000.00015603233
√1e-10 ≈ 0.000010000000015603234
%