計算機科学のブログ

Building Abstractions with Functions - Formulating Abstractions with Higher-Order Functions - Functions as General Methods - Finding fixed points of functions - logarithm

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, step) {
        console.log(`${step} 回目: ${guess} `);
        const next = f(guess);
        return close_enough(guess, next) ?
            next :
            try_with(next, step + 1);
    }
    return try_with(first_guess, 1);
}

console.log(fixed_point(x => Math.log(1000) / Math.log(x), 2));

入出力結果(Terminal, Zsh)

% node answer1.36.js
1 回目: 2 
2 回目: 9.965784284662087 
3 回目: 3.004472209841214 
4 回目: 6.279195757507157 
5 回目: 3.759850702401539 
6 回目: 5.215843784925895 
7 回目: 4.182207192401397 
8 回目: 4.8277650983445906 
9 回目: 4.387593384662677 
10 回目: 4.671250085763899 
11 回目: 4.481403616895052 
12 回目: 4.6053657460929 
13 回目: 4.5230849678718865 
14 回目: 4.577114682047341 
15 回目: 4.541382480151454 
16 回目: 4.564903245230833 
17 回目: 4.549372679303342 
18 回目: 4.559606491913287 
19 回目: 4.552853875788271 
20 回目: 4.557305529748263 
21 回目: 4.554369064436181 
22 回目: 4.556305311532999 
23 回目: 4.555028263573554 
24 回目: 4.555870396702851 
25 回目: 4.555315001192079 
26 回目: 4.5556812635433275 
27 回目: 4.555439715736846 
28 回目: 4.555599009998291 
29 回目: 4.555493957531389 
30 回目: 4.555563237292884 
31 回目: 4.555517548417651 
32 回目: 4.555547679306398 
33 回目: 4.555527808516254 
34 回目: 4.555540912917957 
4.555532270803653
%