Henk Stokhorst writes:
table:1,7,17,23,31,41,47,49,71,73,79,89,97,103,113,119
In case it still isn't clear to someone out there, this is the list of
numbers less than 120 that are relatively prime (no common factors
greater than 1) to 120.
for number := first to last number in table do
for factor := smallest to highest possible factor do
result := Mersenne candidate divided by factor
if result = number then factor found ; exit
next factor
next number
Yes, this is the basic idea.
While I would have expected the code
for factor := smallest to highest possible factor do
result := Mersenne candidate divided by factor
for number := first to last number in table do
if result = number then factor found ; exit
next number
next factor
This is slightly incorrect; the "division" (the actual code does no
long division) still has to take place inside the inner loop:
for factor := smallest to highest possible factor do
for number := first to last number in table do
result := Mersenne candidate divided by (factor + number)
if result = (factor + number) then (factor + number) is a factor ; exit
next number
next factor
to be faster. Of course it isn't, but why?
I believe that most of it is because there is less to do in the
innermost loop. For example, the increase in the possible factor in
the first case is a constant, the index into table doesn't change in
the inner loop, and table isn't even read from in the inner loop.
But it's also not quite that simple. If the Mersenne has one small
factor and it happens to be 119 mod 120, the first method will search
the entire range 15 times before finding it; the second method will
find it quickly and exit. But the assembly code version is so fast -
especially compared to the LL test times for the large exponents GIMPS
is working on now - that it's probably not worth worrying about this
last effect.
Will
