diff options
| -rw-r--r-- | net/ricketyspace/sicp/one/nineteen.scm | 31 |
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))))) |