Combining CPUs

Edmond · 2017-07-02, 22:54

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?

paulunderwood · 2017-07-02, 23:25

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

a1call · 2017-07-03, 01:37

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.

science_man_88 · 2017-07-03, 01:55

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.

a1call · 2017-07-03, 02:25

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.

science_man_88 · 2017-07-03, 02:34

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.

a1call · 2017-07-03, 08:05

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.

science_man_88 · 2017-07-03, 12:04

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.

a1call · 2017-07-03, 13:20

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.

science_man_88 · 2017-07-03, 13:28

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.

a1call · 2017-07-03, 13:42

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.

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 E9B₁₆ 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 3×5×137 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, 02:25	#5
a1call "Rashid Naimi" Oct 2015 Remote to Here/There 3×5×137 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, 08:05	#7
a1call "Rashid Naimi" Oct 2015 Remote to Here/There 3×5×137 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, 13:20	#9
a1call "Rashid Naimi" Oct 2015 Remote to Here/There 3×5×137 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:42	#11
a1call "Rashid Naimi" Oct 2015 Remote to Here/There 3×5×137 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
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