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
Not many can claim 25 years on the Internet! Join us in celebrating this milestone. Learn more about our history, and thank you for being a part of our community!
> (time (prime? 252097800623))cpu time: 1332 real time: 1362 gc time: 391#t
Quote: Original post by neoryder
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!
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.
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.