mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Lounge

Reply
 
Thread Tools
Old 2017-07-02, 22:54   #1
Edmond
 
"Edmond Condillac"
Jul 2017
London

1 Posts
Default Combining CPUs

Is there any way to combine two or more CPUs or motherboards or PCs to make it quicker to process the search for prime numbers, please?
Edmond is offline   Reply With Quote
Old 2017-07-02, 23:25   #2
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

24×229 Posts
Default

Not really. With multi-socket boards it often better to set a prime-hunting program to use one socket per program. The only program I know of that uses multi-sockets well is Primo and that program is for proving primes, not hunting. Also, the scaling of cores used degrades with more threads -- perhaps 4 is optimal. Then there is memory bandwidth to consider. So on your average 4 core box it is advisable to switch off hyperthreading and run 4 real cores when searching for really big primes; Otherwise run 1 program per core. For P-1 factoring of large bleeding edge Mersenne numbers having a great deal of RAM matters. If you have a super-duper graphics card you can also use that to crunch primes. HTH

Last fiddled with by paulunderwood on 2017-07-02 at 23:30
paulunderwood is offline   Reply With Quote
Old 2017-07-03, 01:37   #3
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

2×1,009 Posts
Default

Disclaimer: I have no record primes under my name.
Having said that I still beg to differ.


That is a good question.
The fact that primo can do multithreading is probably an indication that it is not impossible to come up with hardware and software that can use multiple cores/processors/CPUs to test for primality. Primality testing is the main part of finding primes, is it not?

My question is, is LL test parallel-able?

If so then IMHO the most efficient hardware for finding primes would not be a PC, but rather a multiprocessor custom hardware built just for this task. The main challenge with that is the complexity of arbitrary precession capability to be programmed in low levels. Challenging but not impossible.

Last fiddled with by a1call on 2017-07-03 at 01:38
a1call is online now   Reply With Quote
Old 2017-07-03, 01:55   #4
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by a1call View Post
My question is, is LL test parallel-able?
Sure, in theory. All it is ( without regard to primality just the basis of the algorithm), is a connection of values 2 less than the quadratic residues mod a value, strung together. You could, calculate all the quadratic residues-2, restring them together and get an answer. But, to do so, the average one would possibly be as large as the square root of the value being tested so about 35 MB for a 70 million exponent there are about 2^(35 million) of these in theory if no duplicates for x below the square root happen. So to store them all, would take about 35 * 2^35000000 Mb = about 35*10^10536049 Mb or about ... yotta .. yotta bytes ... with a lot of yotta prefixes together just to stop me from needing to flood the forum with the amount.

Last fiddled with by science_man_88 on 2017-07-03 at 02:24 Reason: megabits not megabytes still makes it huge though.
science_man_88 is offline   Reply With Quote
Old 2017-07-03, 02:25   #5
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

201810 Posts
Default

Hey SM, shouldn't you be out and about celebrating Canada day?

Being far from an expert on the LL test,
I believe the action on each loop is a factor of the results of the previous loop.
But it is still perhaps, conceivable to have an architecture where some threads predict the results of earlier loops and fetch the results in case the prediction is true.
But I am open and interested in corrections on this.

Last fiddled with by a1call on 2017-07-03 at 02:26
a1call is online now   Reply With Quote
Old 2017-07-03, 02:34   #6
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by a1call View Post
Hey SM, shouldn't you be out and about celebrating Canada day?

Being far from an expert on the LL test,
I believe the action on each loop is a factor of the results of the previous loop.
But it is still perhaps, conceivable to have an architecture where some threads predict the results of earlier loops and fetch the results in case the prediction is true.
But I am open and interested in corrections on this.
well to prove 7 is prime, using LL in the format I gave would take this:

\{1^2-2\equiv6^2-2\equiv 6, 2^2-2\equiv5^2-2\equiv2,3^2-2\equiv4^2-2\equiv0\} \pmod 7

then stringing these together from a start of 4 we get the next result is 0\pmod 7 and because 2^3-1=7 this happened at the correct time.

Last fiddled with by science_man_88 on 2017-07-03 at 02:40
science_man_88 is offline   Reply With Quote
Old 2017-07-03, 08:05   #7
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

2×1,009 Posts
Default

One predictive behavior is that values with valuations relative to 2, of 3 or more would be very rare and can only occur immediately after the running register is greater than the candidate. Any subsequent values which are less than the candidate will have a valuation relative to 2, of 2 or less. Not a major reduction in the possibilities but perhaps other approaches are feasible.

For example any upcoming running register value can only have 2, or factors of the multiple of the candidate in mod operation, with the current running register value.

Last fiddled with by a1call on 2017-07-03 at 08:15
a1call is online now   Reply With Quote
Old 2017-07-03, 12:04   #8
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by a1call View Post
One predictive behavior is that values with valuations relative to 2, of 3 or more would be very rare and can only occur immediately after the running register is greater than the candidate. Any subsequent values which are less than the candidate will have a valuation relative to 2, of 2 or less. Not a major reduction in the possibilities but perhaps other approaches are feasible.

For example any upcoming running register value can only have 2, or factors of the multiple of the candidate in mod operation, with the current running register value.
this discussion is diverging rapidly from combining CPU's but I'm not even sure what you mean. here's the case for 31 :

\Big{\color {red}1^2-2\equiv30^2-2\equiv 30, 2^2-2\equiv29^2-2\equiv2,3^2-2\equiv28^2-2\equiv7, 4^2-2\equiv27^2-2\equiv 14, 5^2-2\equiv26^2-2\equiv 23,

\color{blue} 6^2-2\equiv25^2-2\equiv3, 7^2-2\equiv24^2-2\equiv16,

\color{red}8^2-2\equiv23^2-2\equiv 0, 9^2-2\equiv22^2-2\equiv17,

\color{blue}10^2-2\equiv21^2-2\equiv5, 11^2-2\equiv20^2-2\equiv26,

\color{red} 12^2-2\equiv19^2-2\equiv18,

\color{blue} 13^2-2\equiv18^2-2\equiv12,

\color{red} 14^2-2\equiv17^2-2\equiv8,

\color{blue}15^2-2\equiv16^2-2\equiv6\Big}

 \pmod {31}

notice anything about the coloring and what happens in those area's.

Last fiddled with by science_man_88 on 2017-07-03 at 12:11
science_man_88 is offline   Reply With Quote
Old 2017-07-03, 13:20   #9
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

2·1,009 Posts
Default

I think you have too many steps combined. My point is any number with a valuation of 3 or more minus 2 will result in a number with a valuation of 2. While valuations of 2 or less can only yield valuations of 2 or less. So for very large numbers, the next number to be squared and subtracted by 2 before it grows larger than the input candidate, it will result in valuations of 2 or less.
All valuations are with respect to number 2.
To clarify further until the mood operation yields the same number which is ether case when the running register is less than input n, the valuations are predictable.
a1call is online now   Reply With Quote
Old 2017-07-03, 13:28   #10
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by a1call View Post
I think you have too many steps combined. My point is any number with a valuation of 3 or more minus 2 will result in a number with a valuation of 2. While valuations of 2 or less can only yield valuations of 2 or less. So for very large numbers, the next number to be squared and subtracted by 2 before it grows larger than the input candidate, it will result in valuations of 2 or less.
All valuations are with respect to number 2.
To clarify further until the mood operation yields the same number which is ether case when the running register is less than input n, the valuations are predictable.
my main point was that an odd number, that produces a value above kp, will have remainder mod 2 that is opposite that of k. So 1^2-2 is between -1*31 and 0 *31 so since -1 is odd 1's remainder will be even, for 3 it produces a value between 0 *31 and 1*31 since 0 is even 3 produces an odd result. 7 is odd and produces a value between 1*31 and 2*31 so it's remainder will be even. same (but opposite) for even numbers. the hard part is knowing which multiples it lands between. Oh,and storage of course.

Last fiddled with by science_man_88 on 2017-07-03 at 13:39
science_man_88 is offline   Reply With Quote
Old 2017-07-03, 13:42   #11
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

2·1,009 Posts
Default

Yes when the mod operation involves subtraction of a multiple of p the result is unpredictable, but as long as it does not involve a subtraction and returns the input value which is the case while p^2 is less than the candidate the result of subtracting 2 is predictable in a chain of any length.
a1call is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Combining low quality random numbers sources only_human Miscellaneous Math 3 2016-05-20 05:47
Combining Msieve with CADO NFS mfeltz Msieve 10 2016-03-16 21:12
cpus running at 10% wildrabbitt Information & Answers 9 2015-01-20 13:31
Whither Older CPUs? Rodrigo Operation Billion Digits 4 2010-10-20 15:12
Combining NewPGen files? roger Riesel Prime Search 4 2008-01-15 00:01

All times are UTC. The time now is 16:52.

Sat May 8 16:52:08 UTC 2021 up 30 days, 11:33, 0 users, load averages: 1.70, 2.25, 2.61

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.