← Back to branch summary

~scompall/+junk/scheme-stuff

« back to all changes in this revision

Viewing changes to sicp-1.scm

  • Committer: Stephen Compall
  • Date: 2011-08-08 23:42:35 UTC
  • Revision ID: scompall@nocandysw.com-20110808234235-k1k3gjbccunr6w7x
O(logn) multiplication from addition

Show diffs side-by-side

added added

removed removed

Lines of Context:
sicp-1.scm
61
61
          ((zero? (modulo exponent 2))
62
62
           (lp (square base) (/ exponent 2) mul))
63
63
          (else (lp base (- exponent 1) (* base mul))))))
 
64
 
 
65
;;; Ex 1.17
 
66
 
 
67
(define (double i)
 
68
  (+ i i))
 
69
 
 
70
(define (halve i)
 
71
  (/ i 2))
 
72
 
 
73
(define (silly-* a b)
 
74
  (let lp ((a a) (b b) (sum 0))
 
75
    (cond ((= b 0) 0)
 
76
          ((= b 1) (+ a sum))
 
77
          ((zero? (modulo b 2))
 
78
           (lp (double a) (halve b) sum))
 
79
          (else
 
80
           (lp a (- b 1) (+ sum a))))))