sicp

sicp sandbox.
git clone git://git.ricketyspace.net/sicp.git
Log | Files | Refs

commit 23011b4d055416fd536b519f8d3d8c48defb0f86
parent 7520b56810dcf0b3766c85ab81fdc22d788f72d5
Author: rsiddharth <s@ricketyspace.net>
Date:   Sat,  1 Apr 2017 15:35:11 +0000

Add (net ricketyspace sicp one nineteen)

Diffstat:
net/ricketyspace/sicp/one/nineteen.scm | 31+++++++++++++++++++++++++++++++
1 file changed, 31 insertions(+), 0 deletions(-)

diff --git a/net/ricketyspace/sicp/one/nineteen.scm 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)))))