mersenneforum.org > Math module 2^p - 1
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2020-08-05, 11:50 #1 wildrabbitt   Jul 2014 3·149 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     Apr 2010 Over the rainbow 23×52×13 Posts one step at a time.
2020-08-05, 13:30   #3
paulunderwood

Sep 2002
Database er0rr

375210 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·33·5·23 Posts An appropriate search term might be "arbitrary precision arithmetic".
2020-08-05, 15:06   #6
paulunderwood

Sep 2002
Database er0rr

23·7·67 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 2·5·72·11 Posts More info on multiprecision multiplication at https://www.mersenneforum.org/showpo...21&postcount=7

 Similar Threads Thread Thread Starter Forum Replies Last Post GP2 Hardware 7 2003-10-02 20:27

All times are UTC. The time now is 06:06.

Sun Jul 25 06:06:32 UTC 2021 up 2 days, 35 mins, 0 users, load averages: 1.54, 1.53, 1.54