Building Abstractions with Functions - Functions and the Processes They Generate - Exponentiation - Fibonacci numbers, clever algorithm, logarithmic number of steps
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.2(Functions and the Processes They Generate)、1.2.4(Exponentiation)、Exercise 1.19の解答を求めてみる。
コード
function double(x) {
return 2 * x;
}
function square(x) {
return x * x;
}
function is_even(n) {
return n % 2 === 0;
}
function fib(n) {
return fib_iter(1, 0, 0, 1, n);
}
function fib_iter(a, b, p, q, count) {
return count === 0 ?
b :
is_even(count) ?
fib_iter(
a,
b,
square(p) + square(q),
double(p * q) + square(q),
count / 2) :
fib_iter(
b * q + a * q + a * p,
b * p + a * q,
p,
q,
count - 1
);
}
console.log(fib(0));
console.log(fib(1));
console.log(fib(2));
console.log(fib(3));
console.log(fib(4));
console.log(fib(5));
console.log(fib(6));
console.log(fib(7));
console.log(fib(8));
console.log(fib(9));
console.log(fib(10));
console.log(fib(100));
入出力結果(Terminal, Zsh)
% node answer1.19.js
0
1
1
2
3
5
8
13
21
34
55
354224848179261900000
%