diff options
author | rsiddharth <s@ricketyspace.net> | 2017-04-01 15:35:11 +0000 |
---|---|---|
committer | rsiddharth <s@ricketyspace.net> | 2017-04-01 15:35:11 +0000 |
commit | 23011b4d055416fd536b519f8d3d8c48defb0f86 (patch) | |
tree | 7c8575dd13c9b4a5726969b4ea6178bc51b06d4c /net/ricketyspace | |
parent | 7520b56810dcf0b3766c85ab81fdc22d788f72d5 (diff) |
Add (net ricketyspace sicp one nineteen)
Diffstat (limited to 'net/ricketyspace')
-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))))) |