Beefy Boxes and Bandwidth Generously Provided by pair Networks
Don't ask to ask, just ask
 
PerlMonks  

Re: Re: This may be more of a math question

by jima (Vicar)
on May 15, 2002 at 21:55 UTC ( #166855=note: print w/ replies, xml ) Need Help??


in reply to Re: This may be more of a math question
in thread This may be more of a math question

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 one-liner that shows the convergence of the series to 1/3 is shown below.

perl -e "$x=0;for $y (1 .. 25) { $x+=(1/4**$y));print $x.chr(10)}" 0.25 0.3125 0.328125 0.33203125 0.3330078125 0.333251953125 0.33331298828125 0.333328247070313 0.333332061767578 0.333333015441895 0.333333253860474 0.333333313465118 0.33333332836628 0.33333333209157 0.333333333022892 0.333333333255723 0.333333333313931 0.333333333328483 0.333333333332121 0.33333333333303 0.333333333333258 0.333333333333314 0.333333333333329 0.333333333333332 0.333333333333333
Edit: changed from 2 ** (2 * x) to 4 ** x, which seems to me to be a bit clearer.


Comment on Re: Re: This may be more of a math question
Download Code

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://166855]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others meditating upon the Monastery: (15)
As of 2015-07-28 16:49 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (258 votes), past polls