Here's my solution so SICP 1.19 (computing fibonacci numbers with a
doubling transform)
;; 1.19
;; T:
;; a = a + b
;; b = a
;;
;; T_pq:
;; a' = ap + (b+a)q
;; b' = bp + aq
;;
;; T_pq^2:
;; a'' = b'q + a'q + a'p
;; = (bp + aq)q + (bq + aq + ap)(p + q)
;; = bpq + aqq + bpq + apq + app + bqq + aqq + apq
;; = (a+b)2pq + (a+b)qq + a(pp + qq)
;; = a(pp+qq) + (b+a)(2pq+qq)
;;
;; b'' = b'p + a'q
;; = (bp + aq)p + (bq + aq + ap)q
;; = bpp + apq + bqq + aqq + apq
;; = b(pp+qq) + a(2pq+qq)
;;
;; Therefore, T_pq^2 = T_(pp+qq)(2pq+qq)
define fib2(n)
fib-iter(1 0 0 1 n)
define fib-iter(a b p q n)
cond
{ n = 0 } b
even?(n) fib-iter(a
b
{square(p) + square(q)}
{{ 2 * p * q } + square(q)}
{ n / 2 })
else fib-iter({{ b * q } + {a * q } + {a * p }}
{{ b * p } + {a * q }}
p
q
{ n - 1 })
I wasn't too happy with how it turned out. For comparison, here's
fib-iter in wart:
def fib-iter(a b p q n)
(if
(iso n 0)
b
even?.n
(fib-iter a
b
(+ square.p square.q)
(+ square.q (* 2 p q))
(/ n 2))
:else
(fib-iter (+ (* b q) (* a q) (* a p))
(+ (* b p) (* a q))
p
q
(- n 1)))
To me this seems more readable. The benefits of curly infix seem
entirely offset by requiring spaces around the operators. I wish it
was closer to C, like:
{b*q + a*q + a*p}
Can y'all think of a nicer way to lay out fib-iter?
Kartik
http://github.com/akkartik/wart#readme
------------------------------------------------------------------------------
Live Security Virtual Conference
Exclusive live event will cover all the ways today's security and
threat landscape has changed and how IT managers can respond. Discussions
will include endpoint security, mobile security and the latest in malware
threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/
_______________________________________________
Readable-discuss mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/readable-discuss
