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

    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  ·  2528 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  ·  2528 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.