Use closed form to calculate Fibonacci numbers for week 112, part 2.

7 files changed, 43 insertions, 56 deletions

diff --git a/challenge-112/abigail/awk/ch-2.awk b/challenge-112/abigail/awk/ch-2.awk
index 5053d8467a..57f4b8cc6f 100644
--- a/challenge-112/abigail/awk/ch-2.awk
+++ b/challenge-112/abigail/awk/ch-2.awk
@@ -9,17 +9,10 @@
 #
 
 BEGIN {
-    cache [0] = 1
-    cache [1] = 1
-}
-
-function fib (n) {
-    if (!(n in cache)) {
-        cache [n] = fib(n - 1) + fib(n - 2)
-    }
-    return cache [n]
+    SQRT5 = sqrt (5)
+    PHI   = (1 + SQRT5) / 2
 }
 
 {
-    print fib($1)
+    print int (0.5 + PHI ^ ($1 + 1) / SQRT5)
 }
diff --git a/challenge-112/abigail/c/ch-2.c b/challenge-112/abigail/c/ch-2.c
index 97c36677ab..73344c2aa5 100644
--- a/challenge-112/abigail/c/ch-2.c
+++ b/challenge-112/abigail/c/ch-2.c
@@ -1,6 +1,6 @@
 # include <stdlib.h>
 # include <stdio.h>
-# include <string.h>
+# include <math.h>
 
 /*
  * See ../README.md
@@ -10,15 +10,14 @@
  * Run as: cc -o ch-2.o ch-2.c; ./ch-2.o < input-file
  */
 
+# define SQRT5 (sqrt (5))
+# define PHI   ((1 + SQRT5) / 2)
+
 int main (void) {
-    int n, f1, f2;
+    int n;
 
     while (scanf ("%d", &n) == 1) {
-        for (f1 = 0, f2 = 1;n --;) {
-            f2 += f1;
-            f1  = f2 - f1;
-        }
-        printf ("%d\n", f2);
+        printf ("%lld\n", (long long) floor (0.5 + pow (PHI, n + 1) / SQRT5));
     }
 
     return (0);
diff --git a/challenge-112/abigail/lua/ch-2.lua b/challenge-112/abigail/lua/ch-2.lua
index db76016a8e..8932952bbd 100644
--- a/challenge-112/abigail/lua/ch-2.lua
+++ b/challenge-112/abigail/lua/ch-2.lua
@@ -5,20 +5,12 @@
 --
 
 --
--- Run as: lua ch-1.lua < input-file
+-- Run as: lua ch-2.lua < input-file
 --
 
-local cache = {}
-cache [0] = 1
-cache [1] = 1
-
-function fib (n)
-    if cache [n] == nil
-    then cache [n] = fib (n - 1) + fib (n - 2)
-    end
-    return cache [n]
-end
+local SQRT5 = math . sqrt (5)
+local PHI   = (1 + SQRT5) / 2
 
 for line in io . lines () do
-    print (fib (tonumber (line)))
+    print (math . floor (0.5 + PHI ^ (tonumber (line) + 1) / SQRT5))
 end
diff --git a/challenge-112/abigail/node/ch-2.js b/challenge-112/abigail/node/ch-2.js
index aa80e0970d..2c06c8fdcd 100644
--- a/challenge-112/abigail/node/ch-2.js
+++ b/challenge-112/abigail/node/ch-2.js
@@ -8,13 +8,11 @@
 // Run as: node ch-2.js < input-file
 //
 
-let cache = {0: 1, 1: 1}
-
-function fib (n) {
-    cache [n] = cache [n] || fib (n - 1) + fib (n - 2)
-    return cache [n]
-}
+let SQRT5 = Math . sqrt (5)
+let PHI   = (1 + SQRT5) / 2
 
   require ('readline')
 . createInterface ({input: process . stdin})   
-. on ('line', _ => console . log (fib (+ _)))
+. on ('line', _ => console . log (
+    Math . round (Math . pow (PHI, +_ + 1) / SQRT5)
+))
diff --git a/challenge-112/abigail/perl/ch-2.pl b/challenge-112/abigail/perl/ch-2.pl
index 2d52916053..09c5717d1c 100644
--- a/challenge-112/abigail/perl/ch-2.pl
+++ b/challenge-112/abigail/perl/ch-2.pl
@@ -18,7 +18,20 @@ use experimental 'lexical_subs';
 #
 
 #
-# This is just the Fibonacci numbers...
+# This is just the Fibonacci numbers. For a staircase of n steps,
+# we need F_(n + 1), where F_n is the nearest integer to
 #
-sub f ($n) {state $c = {0 => 1, 1 => 1}; $$c {$n} //= f ($n - 1) + f ($n - 2)}
-say f ($_) for <>;
+#         n
+#      phi
+#      ----
+#       1/2
+#      5
+#                         1/2
+#                    1 + 5
+# where phi equals   --------  (the golden ratio).
+#                       2
+# 
+#
+my $SQRT5 = sqrt (5);
+my $PHI   = (1 + $SQRT5) / 2;
+say int (1 / 2 + $PHI ** ($_ + 1) / $SQRT5) for <>;
diff --git a/challenge-112/abigail/python/ch-2.py b/challenge-112/abigail/python/ch-2.py
index 3e2a55750d..da542b06f2 100644
--- a/challenge-112/abigail/python/ch-2.py
+++ b/challenge-112/abigail/python/ch-2.py
@@ -5,17 +5,14 @@
 #
 
 #
-# Run as: python ch-1.py < input-file
+# Run as: python ch-2.py < input-file
 #
 
 import fileinput
+from math import sqrt
 
-cache = {0: 1, 1: 1}
-
-def fib (n):
-    if not n in cache:
-        cache [n] = fib (n - 1) + fib (n - 2)
-    return (cache [n])
+SQRT5 = sqrt (5)
+PHI   = (1 + SQRT5) / 2
 
 for line in fileinput . input ():
-    print (fib (int (line)))
+    print (round (pow (PHI, int (line) + 1) / SQRT5))
diff --git a/challenge-112/abigail/ruby/ch-2.rb b/challenge-112/abigail/ruby/ch-2.rb
index 68c59fef40..003d99288f 100644
--- a/challenge-112/abigail/ruby/ch-2.rb
+++ b/challenge-112/abigail/ruby/ch-2.rb
@@ -5,18 +5,13 @@
 #
  
 #
-# Run as: ruby ch-1.rb < input-file
+# Run as: ruby ch-2.rb < input-file
 #
 
-$cache = {}
-$cache [0] = 1
-$cache [1] = 1
-
-def fib (n)
-    $cache [n] ||= fib(n - 1) + fib(n - 2)
-end
+SQRT5 = Math . sqrt 5
+PHI   = (1 + SQRT5) / 2
 
 ARGF . each_line do
     | n |
-    puts (fib(n . to_i))
+    puts ((PHI ** (n . to_i + 1) / SQRT5) . round)
 end