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

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.