Does ECM at yoyo@home exploit base-2 arithmetic?

[R.D. Silverman]

Originally Posted by VBCurtis

It has stalled twice in the last week, so I would say same as ever.

A Query about the YoYo ECM trials:

Is the base 2 modular arithmetic optimization turned on?

Also note that one can optimize arithmetic for 2LM as well. Does GMP-ECM do this?
It is very worthwhile.

e.g. to reduce C mod (2^n-1) put C = A*2^n + B = A*2^n - A + B + A ==
(B + A) mod (2^n-1). Thus, modular reduction only takes a shift and an add.

For C mod (2^n+1) one gets B - A.

to reduce C mod (2^x + 2^y + 1) put C = A*2^x + B. Now add and subtract A*2^y and
add and subtract A: C = A*2^x + A*2^y + A + B -2^y A - A.

Thus C mod (2^x + 2^y + 1) == B - A*2^y - A.

This is much faster than Montgomery multiplication.

[xilman]

Moved here a) because of a request and b) it is more appropriate here anyway.

[mathwiz]

Is this equivalent to asking whether the GMP-ECM binary is built using gwnum?

[R.D. Silverman]

Originally Posted by mathwiz

Is this equivalent to asking whether the GMP-ECM binary is built using gwnum?

Total Non-sequitur. I can't imagine why one might think my question about the internal
ALGORITHM has anything to do with how the code is compiled.

[xilman]

Originally Posted by R.D. Silverman

Total Non-sequitur. I can't imagine why one might think my question about the internal ALGORITHM has anything to do with how the code is compiled.

I find it quite easy to imagine how one might think that the implementation of the arithmetic library may be relevant to your question.

If you want an authoritative answer I suggest that you contact the GMP-ECM developers.

[R.D. Silverman]

Originally Posted by xilman

I find it quite easy to imagine how one might think that the implementation of the arithmetic library may be relevant to your question.

The question was not about the implementation of the library. It was about the
*building* of the library.

If you want an authoritative answer I suggest that you contact the GMP-ECM developers.

This would not tell us whether YoYo invokes the existing "-base2 n" option when it
distributes its wu's.

It is clear that GMP-ECM does not have an option to speed 2LM arithmetic.

[mathwiz]

Originally Posted by R.D. Silverman

Total Non-sequitur. I can't imagine why one might think my question about the internal
ALGORITHM has anything to do with how the code is compiled.

Because my understanding was that gwnum implemented the optimizations you were talking about? See also: https://www.mersenneforum.org/showthread.php?t=14485

[R.D. Silverman]

Originally Posted by mathwiz

Because my understanding was that gwnum implemented the optimizations you were talking about? See also: https://www.mersenneforum.org/showthread.php?t=14485

You asked about how the code was *built*. You did not ask about how it was
implemented.

IT *does* implement fast 2^n-1 and 2^n+1 modular reductions. But that
does not tell us whether YoYo *invokes* the option. I specifically asked
about YoYo's use.

It does not seem to implement fast 2LM arithmetic. Indeed. Fast 2LM arithmetic
can be generalized to fast modular reductions for any moduli with very low Hamming
weight.

[xilman]

Originally Posted by R.D. Silverman

This would not tell us whether YoYo invokes the existing "-base2 n" option when it distributes its wu's.

Fair enough. Why don't you ask yoyo directly?

[henryzz]

I believe that it can autodetect that the base 2 code is needed. I don't know how good it is at that for cofactors.

[R.D. Silverman]

Originally Posted by xilman

Fair enough. Why don't you ask yoyo directly?

Ignorance. I do not know who YoYo is.