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 22·3·37 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 1001011010012 Posts one step at a time.
2020-08-05, 13:30   #3
paulunderwood

Sep 2002
Database er0rr

1101010001002 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

22×3×37 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 25·179 Posts An appropriate search term might be "arbitrary precision arithmetic".
2020-08-05, 15:06   #6
paulunderwood

Sep 2002
Database er0rr

22×3×283 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 441910 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 08:42.

Tue Sep 22 08:42:24 UTC 2020 up 12 days, 5:53, 0 users, load averages: 2.02, 1.79, 1.53