mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Math (https://www.mersenneforum.org/forumdisplay.php?f=8)
-   -   module 2^p - 1 (https://www.mersenneforum.org/showthread.php?t=25803)

 wildrabbitt 2020-08-05 11:50

module 2^p - 1

Hi,

I understand the iteration sequence of the Lucas-Lehmer test involves using
module (2^p-1) arithmetic. How do computers running these such a test cope with numbers with 20+ million digits?

 firejuggler 2020-08-05 13:07

one step at a time.

 paulunderwood 2020-08-05 13:30

[QUOTE=wildrabbitt;552611]Hi,

I understand the iteration sequence of the Lucas-Lehmer test involves using
module (2^p-1) arithmetic. How do computers running these such a test cope with numbers with 20+ million digits?[/QUOTE]

You need a data structure to hold the numbers. The simplest would be a one dimensional [URL="https://en.wikipedia.org/wiki/Array_data_structure#One-dimensional_arrays"]array[/URL] and a byte or two indicating the most significant bit of the number.

For multiplication you use Fast Fourier Transforms (FFT).

Some of the operations can be parallelized across available cores.

Then there is making things cache-friendly.

 wildrabbitt 2020-08-05 14:58

Thanks.

[QUOTE]For multiplication you use Fast Fourier Transforms (FFT).[/QUOTE]

I suppose you mean for calculating the squared term?

 retina 2020-08-05 15:01

An appropriate search term might be "arbitrary precision arithmetic".

 paulunderwood 2020-08-05 15:06

[QUOTE=wildrabbitt;552635]
I suppose you mean for calculating the squared term?[/QUOTE]

Yes. Addition and subtraction and mod 2^p-1 does not require FFT.

 kriesel 2020-08-05 22:38