mersenneforum.org > Math module 2^p - 1
 Register FAQ Search Today's Posts Mark Forums Read

 2020-08-05, 11:50 #1 wildrabbitt   Jul 2014 44710 Posts 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?
 2020-08-05, 13:07 #2 firejuggler     "Vincent" Apr 2010 Over the rainbow 2,683 Posts one step at a time.
2020-08-05, 13:30   #3
paulunderwood

Sep 2002
Database er0rr

5×787 Posts

Quote:
 Originally Posted by wildrabbitt 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?
You need a data structure to hold the numbers. The simplest would be a one dimensional array 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.

Last fiddled with by paulunderwood on 2020-08-05 at 13:54

2020-08-05, 14:58   #4
wildrabbitt

Jul 2014

3×149 Posts

Thanks.

Quote:
 For multiplication you use Fast Fourier Transforms (FFT).

I suppose you mean for calculating the squared term?

 2020-08-05, 15:01 #5 retina Undefined     "The unspeakable one" Jun 2006 My evil lair 2×23×137 Posts An appropriate search term might be "arbitrary precision arithmetic".
2020-08-05, 15:06   #6
paulunderwood

Sep 2002
Database er0rr

5×787 Posts

Quote:
 Originally Posted by wildrabbitt I suppose you mean for calculating the squared term?
Yes. Addition and subtraction and mod 2^p-1 does not require FFT.

 2020-08-05, 22:38 #7 kriesel     "TF79LL86GIMPS96gpu17" Mar 2017 US midwest 134448 Posts More info on multiprecision multiplication at https://www.mersenneforum.org/showpo...21&postcount=7