Add (net ricketyspace sicp one nineteen)

1 files changed, 31 insertions, 0 deletions

diff --git a/net/ricketyspace/sicp/one/nineteen.scm b/net/ricketyspace/sicp/one/nineteen.scm
new file mode 100644
index 0000000..e021b3c
--- /dev/null
+++ b/net/ricketyspace/sicp/one/nineteen.scm
@@ -0,0 +1,31 @@
+;;;; Under Creative Commons Attribution-ShareAlike 4.0
+;;;; International. See
+;;;; <https://creativecommons.org/licenses/by-sa/4.0/>.
+
+(define-module (net ricketyspace sicp one nineteen)
+  #:use-module (net ricketyspace sicp one seventeen)
+  #:export (ifast-fib
+            ifast-fib-iter))
+
+;; Thanks
+;; http://www.billthelizard.com/2010/01/sicp-exercise-119-computing-fibonacci.html
+(define (ifast-fib n)
+  " Compute fibonacci of N.
+
+Iterative version in 𝝝(log N) steps using successive zarking squaring.
+"
+  (ifast-fib-iter 1 0 0 1 n))
+
+(define (ifast-fib-iter a b p q count)
+  (cond ((= count 0) b)
+        ((even? count)
+         (ifast-fib-iter a
+                   b
+                   (+ (* p p) (* q q))
+                   (+ (* q q ) (* 2 p q))
+                   (/ count 2)))
+        (else (ifast-fib-iter (+ (* b q) (* a q) (* a p))
+                        (+ (* b p) (* a q))
+                        p
+                        q
+                        (- count 1)))))