Mersenne: factoring code

[Henk Stokhorst]

Hi,

I once wrote an assembler program on an 2 MHz 8080A processor when it
was state of the art. And then sticked to highlevel programming. I tried
to grasp a little of the factoring assemblycode. I got the impression
that the code is like:


table:1,7,17,23,31,41,47,49,71,73,79,89,97,103,113,119


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


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

to be faster. Of course it isn't, but why?

YotN,

Henk Stokhorst.

Re: Mersenne: factoring code

[Henk Stokhorst]

MR DENNIS S KLUK wrote:

> The table should be :
>
> table:2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,
> 83,89,97,101, 103,107,109,113,127

Eueuhh, different tables I guess, the table contains the sixteen numbers
of the different passes, not primes. I simplified the code a little bit,
it says divide, whereas in the real code fourier transformations seem to
be used. But I assumed more people would be familiar with dividing than
fourier transformatios.

YotN,

Henk Stokhorst.

Mersenne: factoring code

[Will Edgington]

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

Re: Mersenne: factoring code

[Will Edgington]

Henk Stokhorst writes:

   I simplified the code a little bit, it says divide, whereas in the
   real code fourier transformations seem to be used. But I assumed
   more people would be familiar with dividing than fourier
   transformatios.

The factoring code does not use fourier transformations; only the
squaring code of the Lucas-Lehmer test needs that.

But rather than having to even calculate, let alone divide anything
into, the Mersenne number itself, the factoring code (in both Prime95
and the mers package trial factorers) calculates (2^exponent) modulo
the trial factor a bit (literally) of the exponent at a time,
something like this:

  acc = 2;
  topbit = 2;
  while (topbit <= exponent)
topbit = 2*topbit;
  for (bit = topbit/2; bit > 0; bit = bit/2)
acc = (acc*acc) % trial_factor;
if (exponent & bit) /* is this bit set/on in the exponent? */
  acc = 2*acc;
  if (acc == (trial_factor + 1))
found_a_factor(trial_factor);

... where '%' is the C modulo (remainder) operator and '&' is the C
bit-wise and operator.  The comparison to trial_factor + 1 rather than
to just 1 is because the last '2*acc' is not '(2*acc) % trial_factor'.

  Will

Mersenne: factoring code

[Will Edgington]

I wrote:

   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.

Oops!  I should have thought about this some more before sending this
out; it's not quite correct.

All the numbers in this table are indeed relatively prime to 120, but
there are 16 more such numbers, each differing from one of the above
by 60.  My only excuse is that I was thinking in terms of my old,
pre-GIMPS, factoring code, which used 60 instead of 120 but still had
16 entries.  Those 16 out of 60 are equal to (2 - 1)*(3 - 1)*(5 - 1)
out of 2*3*5: cancel half, then one third, then one fifth.

Will