Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon.

Pages: 1-

SICP halp for Nubi

Name: Anonymous 2009-06-01 20:26

Oh wise Lispers and Conjurers of /prog/, I, humble Nubi, seek your enlightenment.  I have started reading SICP, but I'm stuck on an exercise.  I have figured out how to make fast-mult into a logarithmic process, but how do I make it into a tail recursion as well as a logarithmic process?  Here is my code:

; SICP exercise 1-13
; Peasant's algorithm for multiplication
; write a logarithmic iterative process for mult

(define (fast-mult a b)
  (cond ((= b 0) 0)
        ((even? b) (double (fast-mult a (halve b))))
        (else (+ a (fast-mult a (- b 1))))))

(define (double a) (+ a a))
(define (halve a) (/ a 2))

(define (fast-mult2 a b)
  (fast-mult-iter a a b))

(define (fast-mult-iter a n b)
  (cond ((= b 1) n)
        ((and (even? b) (> b 2))
          (fast-mult-iter a (double n) (halve b)))
        (else (fast-mult-iter a (+ a n) (- b 1)))))

(fast-mult 3 2)
(fast-mult2 3 2)
(fast-mult 3 3)
(fast-mult2 3 3)
(fast-mult 3 4)
(fast-mult2 3 4)
(fast-mult 3 5)
(fast-mult2 3 5)
(fast-mult 3 6)
(fast-mult2 3 6)

Name: Anonymous 2009-06-01 20:27

Put the recursive call in tail position.

Name: Anonymous 2009-06-01 20:34

There seems to be two different version of SICP; the exercises in the book that I got from the library are a lot harder than the exercises in the online version.

Name: Anonymous 2009-06-01 21:04

>>1 Is this a troll? nvm IHBT
>>3
The online version is the 2nd edition, your library's version is probably the 1st edition

Name: Anonymous 2009-06-01 21:05

double a instead of n.

Name: Anonymous 2009-06-01 21:15

>>4
OP here. No, I am not a troll.  The problem is a lot harder than it first appears.  The equivalent exercise in the online edition is much simpler:

; Prove that Fib(n) is the closest integer to
; (goldenratio)^n/(sqrt 5), where goldenratio = (1 + (sqrt 5))/2
; for small n.

(define phi (/ (+ 1 (sqrt 5)) 2))
(define psi (/ (- 1 (sqrt 5)) 2))

(define (pow x y count)
  (cond ((= count 1) x)
        ((= count 0) 1)
        (else (pow (* y x) y (- count 1)))))

(define (fib n)
  (fib-iter 1 0 n))

(define (fib-iter a b count)
  (if (= count 0)
      b
      (fib-iter (+ a b) a (- count 1))))

(define (fib-check n)
  (if (= (fib n)
            (/ (- (pow phi phi n) (pow psi psi n)) (sqrt 5)))
      true false))

(fib-check 1)
(fib-check 2)
(fib-check 3)
(fib-check 4)
(fib-check 5)

Name: Anonymous 2009-06-01 22:09

>>1 Maybe I'm just an idiot, but isn't your fast-mult-iter tail recursive?

Name: Anonymous 2009-06-01 23:29

>>7
fast-mult-iter:
✔ O(log n) time
✔ Tail recursive
✘ Performs multiplication

Name: Anonymous 2009-06-02 13:20

OP here.  Here's the correct answer:

(define (fast-mult2 a b)
  (fast-mult-iter a 0 b))

(define (fast-mult-iter a n b)
  (cond ((= b 0) n)
        ((even? b) (fast-mult-iter (double a) n (halve b)))
        (else (fast-mult-iter a (+ a n) (- b 1)))))


If I had read my SICP more carefully, I would have known to keep an invariant quantity that remains the same after each transformation (in this case a*b + n). Thanks >>3

Name: Anonymous 2009-06-02 13:21

>>9
by >>3 I meant >>5

Name: Anonymous 2009-06-02 13:27

(Post truncated.)

Stopped reading right there.

Name: Anonymous 2009-06-02 13:30

Here's another one.  How do I make count-change, which calculates the number of different ways you can make change out a given amount, an iterative process instead of a tree-recursive one?

(define (count-change amount)
  (cc amount 5))
(define (cc amount kinds-of-coins)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (= kinds-of-coins 0)) 0)
        (else (+ (cc amount
                     (- kinds-of-coins 1))
                 (cc (- amount
                        (first-denomination kinds-of-coins))
                     kinds-of-coins)))))
(define (first-denomination kinds-of-coins)
  (cond ((= kinds-of-coins 1) 1)
        ((= kinds-of-coins 2) 5)
        ((= kinds-of-coins 3) 10)
        ((= kinds-of-coins 4) 25)
        ((= kinds-of-coins 5) 50)))

Name: Anonymous 2009-06-02 13:30

(Post truncated.)

Clicked right there.

Name: Anonymous 2009-06-02 13:42

fix your own code you daft fuck

Name: Anonymous 2009-06-02 23:13

>>12

dynamic programming, look it up

Name: Anonymous 2009-06-03 0:29

>>12
Do your own Project Euler exercises.

Name: Anonymous 2010-12-06 9:20

Back to /b/, ``GNAA Faggot''
Don't change these.
Name: Email:
Entire Thread Thread List
All trademarks and copyrights on this site are owned by their respective parties. All comments and posts are the responsibility of their own posters.
- Tinychan + 2ch Mode -