Introduction and Chapter 1

Leviticus Cirrrealus Titanium · 2008-12-18T09:08:37

As of right now, the main text we'll be using is SICP. Please read Chapter One. Until further notice, you'll have until December 31 to read, review, post example code, and ask questions pertaining to the material. Thanks. Please only post about questions pertaining to the Dedication, Preface to the 2nd edition, Preface to the 1st edition, and Chapter 1 in SICP. All other questions such as (but not limited to): compiler setup, which compiler to use, supplemental books, Lisp Vs. Scheme, AI w/ Scheme, Scheme vs. other functional programming languages should be asked in another thread. Thank you for participating [smile] Muhammad Haggag: Changed the title, added links to dedication, preface I and II Muhammad Haggag: Removed time limit from title [Edited by - Muhammad Haggag on May 8, 2007 10:04:29 AM]

SICP Workshop Workshops

Started by Alpha_ProgDes November 14, 2006 04:35 PM

84 comments, last by bodchook 15 years, 4 months ago

SamLowry

1,865

November 29, 2006 02:20 PM

Quote:Original post by Ezbez
Dunno if this is what you were talking about, but I'm able to get similar performance to you (766 ms for 1,000,000 on a 3ghz P4) now that I'm computing (sum 1.0 1000000.0 inverse add-one). I guess that rational-number math is considerably slower. Judging by your clue, this is what you're talking about, though it does involve two characters.

I'll work on the paint problem now.

Yes, that was it. (sum 1. 1000000 inverse add-one) would have worked too, which would amount to one dot :).

SamLowry

1,865

November 29, 2006 02:23 PM

Quote:Original post by Ezbez
Edit: I get that you could paint them all with a finite amount of paint. It seems to level off at about 10.

I just used this function instead of inverse:
(define (area-of-cube a)  (* (inverse a) (inverse a) 6))

That's fully correct too. Mathematica tells me it converges to pi^2.

Ezbez

1,164

November 30, 2006 04:38 AM

The volume of the cubes seems to converge to about 1.202. Definitely could fit in the bag.

My solution to your next problem is this:

;An iterative method(define (years-to-get init-amount rate goal)  (define (iter amount i)    (if (> amount goal)        i        (iter (+ amount (* amount rate)) (+ i 1))))  (iter init-amount 0));A recursive method(define (years-to-get init-amount rate goal)  (if (> init-amount goal)      0      (+ 1 (years-to-get             (+ init-amount (* init-amount rate))            rate goal))))

SamLowry

1,865

November 30, 2006 04:52 AM

Quote:Original post by Ezbez
The volume of the cubes seems to converge to about 1.202. Definitely could fit in the bag.

My solution to your next problem is this:

*** Source Snippet Removed ***

Correct (the > which should be >= in (> amount goal), but that's a detail).

@root

122

December 17, 2006 04:09 PM

I'm having trouble solving exercise 1.16

I find it difficult in general to change procedures that produce a recursive proces to procedures that produce an iterative proces. For example, with exercise 1.11 I had to draw a tree on paper to figure out how to create an iterative proces.
Well that's all fine with me, but now I'm really stuck. I don't really get the point of the invariant. I can see how the powers are reduced in the recursive proces (eg. 15, 14, 7, 6, 3, 2, 1, 0), but I am clueless as to how I can make an iterative proces out of this.

Could anybody give me some pointers?

Anonymous P

429

December 17, 2006 05:22 PM

Quote:
Could anybody give me some pointers?

The point of the invariant is to see the iteration as changing the variables in the invariant in such a way that the invariant, erm, remains invariant. At the end, one of the variables in the invariant will be the answer you seek.

Let's say we want to find the answer to b ^ n0. Our iterative version will use three variables: a, b and n. The invariant will be the expression:

a * (b ^ n)	;; In general= 1 * (b ^ n0)	;; The initial condition=a * (b ^ 0)	;; The stop condition

Obviously, when n=0, a = b ^ n0 must hold, and a is the answer we seek.

Our algorithm will change the values of a and n until the halting condition (n = 0) holds.

IF our iterative algorithm preserves the invariant a * (b ^ n) at every step, then a MUST be the correct answer when n = 0.

That's why the invariant is useful. Now, all that remains is to find a way so that n gets smaller at each step and a gets larger in a way that preserves the invariant.

The recursive version should give you a BIG hint on how to do this.

SamLowry

1,865

December 18, 2006 08:46 AM

Quote:Original post by @root
I find it difficult in general to change procedures that produce a recursive proces to procedures that produce an iterative proces. For example, with exercise 1.11 I had to draw a tree on paper to figure out how to create an iterative proces.

Making your functions tail-recursive (i.e. so that they generate iterative processes) is something that you'll have to learn by practice and will become second nature after a while. Chapter 2 will introduce lists, it'll be easier then to provide you with some interesting exercises.

@root

122

December 18, 2006 04:01 PM

@ Anonymous P
Awesome. That actually makes sense :)
Going with your advice, I come to this:

(define (fast-expt b n)  (define (iter b n a)    (cond ((= n 0) a)          ((even? n) (iter b (/ n 2) (* a (fast-expt b (/ n 2)))))          (else (iter b (- n 1) (* a b)))))  (iter b n 1))            (define (even? n)  (= (remainder n 2) 0))

Would that be an acceptable implementation? I wasn't totally sure if the call to fast-expt was defying the purpose, but the procedure seems to produce theta of (n) steps and as far as I can see, it looks like an iterative proces.

@ SamLowry
I'll just keep on practicing, then. Looking forward to Chapter 2 :)

[Edited by - @root on December 18, 2006 4:01:14 PM]

Anonymous P

429

December 18, 2006 04:54 PM

Quote:
Would that be an acceptable implementation? I wasn't totally sure if the call to fast-expt was defying the purpose, but the procedure seems to produce theta of (n) steps and as far as I can see, it looks like an iterative proces.

The call to fast-expt inside the even case IS a (non-tail) recursive call to iter. So, not quite.

But you're ALMOST there. You've got the odd case right: there are no calls to iter (or fast-expt) inside of the parameters passed to iter, so iter in the odd case is tail-recursive and hence the compiler can turn it into a constant-space iteration.

What about the even case?

Remember,

b ^ n = (b ^ n / 2) ^ 2 = (b ^ 2) ^ (n / 2)So if a0, b0 and n0 are the parameters to iter, the following assignments:b = b0 ^ 2n = n0 / 2a = a0 preserve the invariant and eventually get rid of even n's by factoring out the 2's and plonking them into b.Let's prove the invariant is preserved:a * b ^ n=a0 * ((b0 ^ 2) ^ (n0 / 2))=a0 * (b0 ^ (2 * (n0 / 2)))=a0 * (b0 ^ n0)

I didn't mention b changing in my previous post, so maybe that mislead you.

@root

122

December 18, 2006 05:47 PM

Ahhh... I can truly be an idiot at times. Indeed, I did forget that b can be transformed as well, in order to preserve the invariant.
Well, that clears things up. Thanks again!

Introduction and Chapter 1

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Introduction and Chapter 1

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines