summaryrefslogtreecommitdiffstats
path: root/net/ricketyspace
diff options
context:
space:
mode:
authorrsiddharth <s@ricketyspace.net>2017-04-01 15:35:11 +0000
committerrsiddharth <s@ricketyspace.net>2017-04-01 15:35:11 +0000
commit23011b4d055416fd536b519f8d3d8c48defb0f86 (patch)
tree7c8575dd13c9b4a5726969b4ea6178bc51b06d4c /net/ricketyspace
parent7520b56810dcf0b3766c85ab81fdc22d788f72d5 (diff)
Add (net ricketyspace sicp one nineteen)
Diffstat (limited to 'net/ricketyspace')
-rw-r--r--net/ricketyspace/sicp/one/nineteen.scm31
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)))))