mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2020-08-05, 11:50   #1
wildrabbitt
 
Jul 2014

22×3×37 Posts
Default 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?
wildrabbitt is offline   Reply With Quote
Old 2020-08-05, 13:07   #2
firejuggler
 
firejuggler's Avatar
 
Apr 2010
Over the rainbow

240910 Posts
Default

one step at a time.
firejuggler is online now   Reply With Quote
Old 2020-08-05, 13:30   #3
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

22·3·283 Posts
Default

Quote:
Originally Posted by wildrabbitt View Post
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
paulunderwood is online now   Reply With Quote
Old 2020-08-05, 14:58   #4
wildrabbitt
 
Jul 2014

22·3·37 Posts
Default

Thanks.



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

I suppose you mean for calculating the squared term?
wildrabbitt is offline   Reply With Quote
Old 2020-08-05, 15:01   #5
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

25×179 Posts
Default

An appropriate search term might be "arbitrary precision arithmetic".
retina is offline   Reply With Quote
Old 2020-08-05, 15:06   #6
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

22×3×283 Posts
Default

Quote:
Originally Posted by wildrabbitt View Post
I suppose you mean for calculating the squared term?
Yes. Addition and subtraction and mod 2^p-1 does not require FFT.
paulunderwood is online now   Reply With Quote
Old 2020-08-05, 22:38   #7
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

114316 Posts
Default

More info on multiprecision multiplication at https://www.mersenneforum.org/showpo...21&postcount=7
kriesel is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Pentium V may have optional 64-bit "module" GP2 Hardware 7 2003-10-02 20:27

All times are UTC. The time now is 08:45.

Tue Sep 22 08:45:40 UTC 2020 up 12 days, 5:56, 0 users, load averages: 2.34, 1.90, 1.62

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.