計算機科学のブログ

Building Abstractions with Functions - Formulating Abstractions with Higher-Order Functions - Functions as General Methods - Finding fixed points of functions - golden 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.3(Formulating Abstractions with Higher-Order Functions)、1.3.3(Functions as General Methods)、Exercise 1.35の解答を求めてみる。

  • x = 1 + 1 / x
  • x^2 = x + 1
  • x^2 - x - 1 = 0

この方程式の正の解は

  • x = (1 + √5) / 2

以上より、不動点は黄金比。

コード

const tolerance = 0.00001;
function fixed_point(f, first_guess) {
    function close_enough(x, y) {
        return Math.abs(x - y) < tolerance;
    }
    function try_with(guess) {
        const next = f(guess);
        return close_enough(guess, next) ?
            next :
            try_with(next);
    }
    return try_with(first_guess);
}

const golden_ratio = fixed_point(x => 1 + 1 / x, 1);

console.log(golden_ratio);

入出力結果(Terminal, Zsh)

% node answer1.35.js
1.6180327868852458
%