Re: SF: Back to theory

From: Tim Peters (tim.one_at_comcast.net)
Date: 02/28/05 

Date: Mon, 28 Feb 2005 11:00:48 -0500

Filling in some details about the expected behavior of the random f-g
algorithm:

[Tim Peters]
[...]
> Sanity check: Here's a run against an implementation that _does_ pick
> f and g at random repeatedly, from 1..M-1, until gcd(f-g, M) reveals a
> factor.
> ...
> nbits 15: 1000 of 1000 factored, 100%
> gcds: actual 11,658,968 expected random 12,083,917 no factor 0
> algorithm beat random-gcd 631 of 1000 factoring cases
> random - actual: min -82310
> mean 424.949
> max 15385
> median(s) [4044, 4094]
>
> So those were within spitting distance. It was a surprise to me that
> the actual algorithm beat the theoretical one in 63% of the trials, but
> on reflection something close to that is expected.
> ...
> the "# of trials until first success" statistic follows the
> geometric distribution
> ...
> A "typical" example for that run was p=32633 and q=19993. The
> probability of success on a trial is then (p+q-2)/(M-1) ~= 8.0658e-5,
> and the probability of failure y = 1-x ~= 0.999919342. The mean # of
> trials before success is 1/x ~= 12398. The probability that we'll
> succeed before 12398 trials is the sum for i in 1..12397 of
> y^(i-1)*x ~= 0.632. That's suspiciously close to the 631/1000 observed,
> ...

In general, as x (the probability of success per trial) approaches 0, the
probability that we'll succeed at or before the 1/x'th (mean) trial
approaches 1-1/e ~= 0.632. The median (half the time we'll succeed before
this trial, half the time after) is the log base 1-x of 1/2. For the
example above, that's ~8593. Those are easy derivations, so I won't spell
them out here.

Changing the driver to say "algorithm beat random-gcd" iff the actual # of
gcds used is < log(0.5)/log(1-x) (instead of < 1/x) then gave:

    nbits 15: 1000 of 1000 factored, 100%
    gcds: actual 11,992,743 expected random 11,945,542 no factor 0
    algorithm beat random-gcd 505 of 1000 factoring cases
    ...

I'll keep that change, since it was my _intent_ on the "algorithm beat
random-gcd" line to count the number of times it beat the expected median,
not the expected mean, and it's less prone to confusion for "looks random"
to mean "about half the time". "505 of 1000" reads as "may as well flip a
coin" a lot more obviously than "631 of 1000"!