This might help you.

The simplest way to measure how long a computation takes is uses time:

> (time (prime? 252097800623))cpu time: 1332 real time: 1362 gc time: 391#t

Hi all,

Thanks SamLowry for the link! It was extremely useful.

I was half expecting no one was checking this thread anymore!

Nice to know someone is still checking the chapter one thread!

I started this book last week and I'm trying to work through all of the exercises. I'm having trouble visualizing the count-change procedure in Chapter 1.2.2. I tried stepping through the execution with small values for amount, but I'm getting lost! I was going to draw the tree structure out but it's complicated even for small values of amount. I mean, I understand the concept (I don't know if I would have thought to do it this way without seeing it in the book first, but the idea of breaking it into a - d recursively does make sense) but it's almost like I have to just *believe* the procedure works because it implements the algorithm which I _intuitively_ know will work, but is too confusing to follow to *make sure* it works!

I did some research last night and spent some time mulling over the problem above. I think I understand it now. I figured I would update this post with my thoughts in case anyone is interested. GameDev has a good article about recursion, which has the exact change counting algorithm from SICP.

So basically, the article mentioned above walks through a simple case of making change for $.10 using dimes, nickels, and pennies. See below:

Quote:
To convince you that the reduction and boundary cases work, lets look again at the 10 cent problem (note that we're not interested in 25 and 50 cent coins in this case): So, to change 10 using the coins 10, 5 and 1 (ordered thus) we sum (1) the number of ways to change 10 using all but the first kind of coin, that is using 5 and 1 only, and (2) the number of ways to change amount 10 - 10 = 0 using all kinds of coins. (2) Is simple - there's one way to change amount 0 (by the first boundary case). (1) can be further reduced to (3) the number of ways to change amount 10 using 1 cent only, plus (4) the number of ways to change 10 - 5 = 5 using all kinds of coins. (3) Is only one way, ten 1 cent coins, (4) can be reduced, etc. (we get two ways from (4) - one five cent coin, and five one cent coins). When the algorithm finishes we'll end up with 4 ways.

OK, this makes sense. If I owe you 10 cents, I can give you a dime, and be done. Or if I don't have any dimes, I can give you 10 pennies. If I don't have 10 pennies, I can give you 1 nickel and 5 pennies, or I can give your 2 nickels. And this follows exactly from the algorithm:

Quote:
The number of ways to change amount a using n kinds of coins equals

* the number of ways to change amount a using all but the first kind of coin, plus

* the number of ways to change amount a - d using all n kinds of coins, where d is the denomination of the first kind of coin.

I see how this becomes a tree structure, because each call to count-change results in two more calls to count-change until the base-case is reached. The base cases in the algorithm are we have ran out of coins (n = 0), we have made change to 0 (a = 0), or we have given too much change (a < 0).