Beefy Boxes and Bandwidth Generously Provided by pair Networks
There's more than one way to do things
 
PerlMonks  

This may be more of a math question

by Fingo (Monk)
on May 15, 2002 at 21:03 UTC ( #166848=perlquestion: print w/replies, xml ) Need Help??

Fingo has asked for the wisdom of the Perl Monks concerning the following question:

This is taken straight from the documentation for srand
Frequently called programs (like CGI scripts) that simply use

time ^ $$

for a seed can fall prey to the mathematical property that

a^b == (a+1)^(b+1)

one-third of the time. So don't do that. 
I don't quite understand what the author meant, but this does not seem possible. Is this a mistake, or am I misunderstanding what is meant?
Thanks,
 	Max

Replies are listed 'Best First'.
Re: This may be more of a math question
by Corion (Pope) on May 15, 2002 at 21:18 UTC

    Well, it's simply true - we need first to look at the lowest bit of a and b. If they are both zero, then, obviously, a^b == (a^b) + (1^1) == (a+1)^(b+1).This occurs 25% of the time.

    The next (interesting) case would be that both lowest bits of a and b are 1, and the second lowest bit of both, a and b, is 0. Then again, a^b == (a+1)^(b+1).

    I'm not sure, if this method of counting will arrive at 33% overall, as there are some other possibilities (like a=5, b=6) which I didn't count, but 25% is close enough to 33% to mark this method of generating random numbers as dangerous.

    perl -MHTTP::Daemon -MHTTP::Response -MLWP::Simple -e ' ; # The $d = new HTTP::Daemon and fork and getprint $d->url and exit;#spider ($c = $d->accept())->get_request(); $c->send_response( new #in the HTTP::Response(200,$_,$_,qq(Just another Perl hacker\n))); ' # web
      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.
Re: This may be more of a math question
by buckaduck (Chaplain) on May 16, 2002 at 12:19 UTC
    Just in case...

    Perhaps you misunderstand the ^ operator? That's the XOR operator, although many people mistakenly assume it's the exponent operator. Exponents are done with the ** operator. See perlop.

    Update: Ah, slow typing will be the death of me someday...

    buckaduck

Re: This may be more of a math question
by Anonymous Monk on May 16, 2002 at 12:05 UTC
    Note also that ^ is XOR in perl, not exponentiation (which would be ** ).

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://166848]
Approved by Corion
Front-paged by MeowChow
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others imbibing at the Monastery: (3)
As of 2020-10-27 07:02 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    My favourite web site is:












    Results (256 votes). Check out past polls.

    Notices?