Proving optimized function is still correct

[Michal Wallace]

On Mon, 12 Nov 2001 salvasan at yahoo.com wrote:

> def count_combos_optimised( m, n ):
>     numer = 1
>     denom = 1
>     j = m+n-1
>     i = 1
>     while i<m:
>         numer = numer * j
>         denom = denom * i
>         j = j - 1
>         i = i + 1
>     return numer/denom
> 
> I've tried a whole bunch of values for m and n and so far both
> functions return identical results.
> 
> count_combos( 6, 4 ) and count_combos_optimised( 6, 4 ) both return 126
> 
> The optimised version operates a lot faster, but how can I be sure
> that count_combos_optimised( m, n ) and count_combos( m, n ) will
> return the same values for every possible pairing of positive integers
> (m,n) ? There could very well be some pair of six digit numbers upon
> which they disagree, or maybe no such pair exists, but is there a way
> to tell either way?


How do you know the first version works?

Her code looks a whole lot simpler than the first version, but reading
it still makes my head want to explode...

The code doesn't really convey what it's trying to accomplish.  You're
counting combinations of something... Well great... But what does that
mean?

I'd wager that the reason you have a hard time knowing whether the
functions do the same thing is that they don't map well with the way
you're thinking about the problem... Or they don't communicate back
to you what they're doing.

This is the kind of place where comments come in really handy.
Go back over each line and think about WHY it's doing what it's
doing... And add it as a comment. 

As far as I know, the only way to validate stuff like this without
testing every possible value is to come up with an algebraic
description of what you want, prove that it works through logical
deduction [remember proofs from geometry class?] and then prove that
what you've written matches the algebraic description.

It may be that you'd be better off writing this kind of thing in a
more functional style. It may or may not speed things up, but it
would probably make you a lot more confident that it really does
what you think it does.

Or, you could ask yourself... Does it really matter if the function
fails for m= 928347932874932874 and n=239847923479234872348323?
(Maybe it does... That's not for me to say.)

Cheers,

- Michal
----------------------------------------------------------------------
let me host you! http://www.sabren.com       me: http://www.sabren.net
----------------------------------------------------------------------