SICP - counting change

In section 1.2.2, SICP gives an incredibly inefficient recursive procedure for counting change and then later leaves it up to the reader to come up with a better one.

Here's what I was able to come up with (in Python because I like it better than Scheme):


def count_change(n):
    n /= 5
    if n%2:
        b = -1
    else:
        b = 1
    c = 1425*b + 26799 + n*(150*b + 21850 + n*(4760 + n*(380 + 10*n)))
    m = n%10
    if m==0 or m==1:
        c -= 4224
    elif m==2:
        c += (576+480*n)
    elif m==3 or m==8:
        c -= 384
    elif m==4:
        c -= (1344+480*n)
    elif m==5 or m==6:
        c += 5376
    elif m==7:
        c += (7776 + 480*n)
    elif m==9:
        c -= (8544 + 480*n)
    c /= 24000
    return c

I attempted to solve the recurrence relation exactly (lots of complicated sums involving roots of unity to simplify). I haven't proven that the above is indeed correct, but it seems to work well for all the values I've tested.

O(1) for the win.

THIS PRESSURE... IS IT FAIRX THE HAXXOR??

>>26
Mods stop by once in a while (two times a year) and clean up some spam, sometimes I get banned and have to get a new IP.

Unfortunately they (only one, perhaps MrVacBob?) only go to /prog/ ;)