Welcome to the Monastery  
PerlMonks 
Re: Re: This may be more of a math questionby jima (Vicar) 
on May 15, 2002 at 21:55 UTC ( #166855=note: print w/replies, xml )  Need Help?? 
Yeah, you got it. You just needed to take it a little further to prove it.
When the lowest bit for a and b is 0, then the formula is equal, which happens, as you say, 25% (1/4) of the time. When the lowest bits for a and b are 01, the formula is equal. This happens 1/16 of the time (there are 16 possible combinations of the lowest 2 bits of 2 variables, and only this particular combo will give you a problem). So let's say the lowest two bits of both variables are 11. If the next bit is 0 (making the lowest bits of each variable 011), then the formula is equal 1/64 of the time (64 combinations of the lowest 3 bits of 2 variables). The math majors in the audience will look for a pattern and realize that, to figure out the total probability that the equation will be equal, they just need to sum up the series (1 / (4 ** x)), where x goes from 1 to the number of bits in yer integer. A Perl oneliner that shows the convergence of the series to 1/3 is shown below. Edit: changed from 2 ** (2 * x) to 4 ** x, which seems to me to be a bit clearer.
In Section
Seekers of Perl Wisdom

