On Tue, Aug 28, 2012 at 7:16 AM, Kartik Agaram <a...@akkartik.com> wrote:
> 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}
This is indeed an issue. But * and + have traditionally been
legitimate characters for symbols in Lisp. Hence conventions such as
*foo* for global variables, using - to separate words in an identifier
(as opposed to _ in most other languages, or camelCase)
>
> Can y'all think of a nicer way to lay out fib-iter?
One trick is to avoid getting into n-expr or c-expr as much as you can
get away with.
;view in a fixed-width font
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 }
Sincerely,
AmkG
------------------------------------------------------------------------------
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
Readable-discuss@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/readable-discuss
