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

I remember reading SICP. It's a lot of fun.

The recursive algorithm reminds me of something I was just looking at the other day, the Chu-Vandermonde identity.

One obvious way to speed it up is memoization. But I wonder if that would be as effective in this case as for Fibonacci.

Another way would be to just handle the penny case by just outputting 1 straight away if amount >= 0, and handle the penny-and-nickel case by outputting 1+floor(amount/5). I'd imagine that just doing this would speed up the program quite a bit.

But a straight-up, non-recursive calculation in one fell swoop? I'm not sure how to do that.

bhrgunatha  ·  2491 days ago  ·  link  ·  

    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  ·  2490 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  ·  2489 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  ·  2489 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  ·  2489 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.

dingus  ·  2496 days ago  ·  link  ·  

After about an hour trying to make an iterative algorithm I was unable to do so. I though I had it, but it turns out I didn't.