a thoughtful web.
Good ideas and conversation. No ads, no tracking.   Login or Take a Tour!
comment by bhrgunatha
bhrgunatha  ·  2830 days ago  ·  link  ·    ·  parent  ·  post: A nice problem from SICP

    But I wonder if that would be as effective in this case as for Fibonacci.

Sure, why not? It's still tree recursion after all. You just have to use an extra procedure that takes the change amount and how many coin values you have.

e.g. For the UK coin values are 1, 2, 5, 10, 20, 50, 100 and 200 so there are 8 coin values.

So instead of


you'd use


cc(amount, num_coins)

and you memoize cc with indexes of amount and num_coins

yakov  ·  2829 days ago  ·  link  ·  

You're right. I hadn't quite thought it through, but it would work well: eg. for 8 coin values, if you need to calculate the number of ways to make 2.00, you need to make at most 200*8=1600 calls to the recursive function. So you get O(n) efficiency.

But it still seems like you should be able to do better: O(1) would be possible with a closed-form formula.

edit: Oh, I noticed you actually implemented it with memoization. Great!

bhrgunatha  ·  2829 days ago  ·  link  ·  

    O(1) would be possible with a closed-form formula.

That's way beyond my maths ability. Do you think you could find such a formula?

I know there's Binet's formula for Fibonacci, but it's impractical for larger numbers as the floating point errors start to affec tthe results (on most machines anyway.)

yakov  ·  2829 days ago  ·  link  ·  

Yeah, it's tough, I don't really know how to go about it. But here's at least a demonstration for three denominations, {1, 2, 5}: (n is the total amount to add up to)

    def onetwofive(n):

numfives = math.floor(n/5.)+1

return int( numfives * (n % 5 + n + 3)/4 - (numfives % 2) * (n % 2 - 0.5) / 2. )

Disgusting, I know! But it works: I double checked it against your code, it gives the same result up to n=5000.

An estimate for four denominations {1, 2, 5, 10} is n^3/600; for five denominations {1, 2, 5, 10, 25}, n^4/60000. I got these by summing crudely and dropping low order terms. They seem to be asymptotic: the estimate for five denominations is accurate to within 5% of the true value for n > 2000. That might seem silly but count_change does get quite slow for n >> 10^6 (that's $10,000.00), while the approximation is good to within 0.01%.

edit: You could write a program that returns an estimator function for a given set of denominations. See Faulhaber's formula.

bhrgunatha  ·  2828 days ago  ·  link  ·  

I'm impressed you managed a solution for 3 coins.

> count_change does get quite slow for n >> 10^6 (that's $10,000.00)

From a pure math angle, both memo & dynamic programming versions are linear in time and space. As you said though, those numbers are growing exponentially meaning the space will grow exponentially too.