mersenneforum.org Combining CPUs
 Register FAQ Search Today's Posts Mark Forums Read

 2017-07-02, 22:54 #1 Edmond   "Edmond Condillac" Jul 2017 London 1 Posts 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?
 2017-07-02, 23:25 #2 paulunderwood     Sep 2002 Database er0rr 24×229 Posts 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
 2017-07-03, 01:37 #3 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 2×1,009 Posts 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
2017-07-03, 01:55   #4
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 Originally Posted by a1call 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.

 2017-07-03, 02:25 #5 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 201810 Posts 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
2017-07-03, 02:34   #6
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by a1call 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

 2017-07-03, 08:05 #7 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 2×1,009 Posts 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
2017-07-03, 12:04   #8
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 Originally Posted by a1call 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

 2017-07-03, 13:20 #9 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 2·1,009 Posts 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.
2017-07-03, 13:28   #10
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by a1call 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

 2017-07-03, 13:42 #11 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 2·1,009 Posts 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post only_human Miscellaneous Math 3 2016-05-20 05:47 mfeltz Msieve 10 2016-03-16 21:12 wildrabbitt Information & Answers 9 2015-01-20 13:31 Rodrigo Operation Billion Digits 4 2010-10-20 15:12 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