λ Fibonacci - doubling

======= Algorithm ======= <syntax js> function fib(n) { if (n <= 0) { return 0; } else { return fib2(n-1)[1]; } } // Returns a tuple (F(n), F(n+1)) function fib2(n) { if (n <= 0) { return [0, 1]; } else { var ab = fib2(Math.floor(n / 2)); var a = ab[0], b = ab[1]; var c = a * (2 * b - a); var d = b * b + a * a; if (n % 2 == 0) { return [c, d]; } else { return [d, c + d]; } } } </syntax> ======= Support ======= <syntax js> function run(args) { delete result; result = fib(args.n); } </syntax> ======= Tests ======= <syntax js> function testTen() { assert (fib(10) === 55, "fib(10)"); } function testEighteen() { assert (fib(18) === 2584 , "fib(18)"); }</syntax> ======= Options ======= <syntax js> { "title":"Fibonacci - doubling ", "height":"420px" } </syntax> ======= Visualisation ======= <syntax html> <html> <head> <style type="text/css"> input {width:50px;} </style> <script type="text/javascript"> function update(n, x) { var element = document.getElementById("result"); var result = x.lookupInScope("result"); var n = x.lookupInScope("n"); if (typeof result != "undefined") { element.innerHTML = "= "+result; } else if (n) { element.innerHTML = "Calculating fib("+n+")"; } else { element.innerHTML = ""; } } function args() { var n = document.getElementById('n').value; return {n:n}; } </script> </head> <body> fib( <input id="n" value=12> ) <div id="result"></div> </body> </html> </syntax>