> Those times are awfully small

I also ran it with more iterations but the ranking remains about the
same.

> For example, I have a test that I've been using, which combines
> Phrogz's, vsv's, and some of my own.

I also have an extended set of test cases that builds on whatever was
posted to the list. For this comparison I only selected test cases
for
which a sufficient number of solutions returned results in finite
time
(I'm doing this on a 4-yrs old notebook, so time is limited :-).

> And that gives a different sense

This is also about what I get when I run phrogz's test cases. But
these
test cases don't seem representative somehow. phrogz's cases are
rather
suited to test the program's correctness not so much to measure its
general performance I'd say. (BTW I would never claim that my
solution
is in general 19 times faster than anyone of other solution in all
possible situations. I know my code well enough to know how to make
it
run in circles for quite some time.)

In a "natural" setting, I think something like this

    default_change = [25, 10, 5, 1]
    30.times do |a|
        make_change(a ** 2, default_change)
    end

is more likely to be a problem the program has to solve. So, my
reasoning is that a good solution should solve these standard cases
fast
and should not go wild on "strange" input, which my first solution
does
with certain input. (But most other solutions do too.)

I also think all solutions in this listing perform pretty well on
these
general cases. This would become obvious if one included a brute
solution that always does a full search.

I think Paolo's solution is cool because it's really compact, because
it
avoids recursion and because it doesn't need to include optimizations
for special cases. My solution on the other hand needs special case
handling in order to avoid deep recursion, which ruby19 doesn't like
too
much as it seems. But then, with "normal" input the number of
recursions
should be limited since coin values are usually selected in a way to
make it easy for people to give change. This probably is the reason
for
why there aren't any 17cent coins around -- which would be fun
though.
So maybe a depth-first search is the more appropriate approach for
this
problem after all. Or maybe not?

Anyway, I said this listing is rather subjective, didn't I.

Regards,
Thomas.