Neural network prime finding

[GP2]

Originally Posted by airsquirrels

Or, just pipe those 32 bits, or the bits of the whole number into a neural net and train it to recognize primes. Surely someone has at least experimented with that.

I don't think there's any mathematical basis for that.

[science_man_88]

Originally Posted by GP2

I don't think there's any mathematical basis for that.

In some cases of weeding out composites, there are. For example 101101 in base 2, is divisble by 101 (aka 5). So fully repeated units( other than all of length 1) throughout is composite.

[kriesel]

Originally Posted by GP2

I don't think there's any mathematical basis for that.

There's precedent, literally. Or was there? The article speculates they were mentally sieving for low primes. http://www.pepijnvanerp.nl/articles/oliver-sackss-twins-and-prime-numbers/

[kriesel]

Originally Posted by science_man_88

In some cases of weeding out composites, there are. For example 101101 in base 2, is divisble by 101 (aka 5). So fully repeated units( other than all of length 1) throughout is composite.

Maybe I'm missing your point, but we already know to not bother with composite exponents when looking for Mersenne Primes.
If q=ab, 2^q-1 = 2^(ab)-1 has factors 2^a-1 and 2^b-1. Consider a=3, b=5.
The binary expression is 111 111 111 111 111 (77777 octal) or 11111 11111 11111.
A special case of repdigit numbers.
Similarly you can tell the decimal numbers below are factorable at a glance:
22
333
44
5555
66666
777
8888
9999

[airsquirrels]

Originally Posted by kriesel

There's precedent, literally. Or was there? http://www.pepijnvanerp.nl/articles/...prime-numbers/

The concept was that running prime95 on an exponent is essentially a black box that takes < 32 bits as its input and outputs a Boolean true or false. You could generate a theoretical Boolean circuit that performed this calculation, regardless of how infeasibly large it would be in practice. If you could find the minimal possible such circuit through brute force you would have found the best possible algorithm, even though you could not necessarily understand its methods. Although you would have to differentiate optimizing for algorithms with the shortest-longest path for speed vs generated looping circuits that may be quick small.

Isn’t a trained neural network with N nodes not so dissimilar? In this case the minimum number of nodes that could provide the correct answer may indeed be very large.

[axn]

Originally Posted by airsquirrels

The concept was that running prime95 on an exponent is essentially a black box that takes < 32 bits as its input and outputs a Boolean true or false.

If we know all the mersenne primes exponents < 2^32, sure. But you're thinking of training with the known 50 and using them to discover the remaining, yes? How will it work? After training, we feed it each of the remaining exponent one by one, and it will spit out a yes/no answer, right?

But how can we know that it is correct? Obviously, we will have to test every "yes" answer with LL/PRP test. Doesn't sound too bad. But how can we be sure that it didn't miss out any primes? Oops. Now we gotta test every "no" answer as well with LL/PRP. The problem is that the NN prediction is indeed a black box and as such, does not constitute mathematical proof.

If such an NN could be built (and I seriously doubt it -- I think prime prediction is a poor domain for NN), at best it will accelerate some prime finds (because we can cherry pick its "yes" predictions for initial tests), but overall there will be no savings.

EDIT:- In fact, we can try building a much simpler NN which will predict the nth prime. The advantage here is that we have a large training data set, and it is very easy to validate its predictions. I predict that it will be a miserable failure (i.e. success < 99%.)

[airsquirrels]

Originally Posted by axn

EDIT:- In fact, we can try building a much simpler NN which will predict the nth prime. The advantage here is that we have a large training data set, and it is very easy to validate its predictions. I predict that it will be a miserable failure (i.e. success < 99%.)

I should be clear I only mentioned this as a thought exercise not a serious pursuit.

That said I also figured you’d try to build it as a general prime generator. Let’s say we give it 128 bits of input and train it against 50% of those primes. Or more precisely, we increase the number of nodes gradually and document the success rate of its detection of the rest of the set. Wouldn’t this data give an interesting bit of insight into the complexity of the best prime finding algorithm?

Someone must have explored this or other such simpler problems (can I document the size of a neural net with 64 (2x32) inputs and 64 outputs needed to successfully be trained as a multiplier?). Of course you could replace the word neural net with Boolean circuit, except it is hard (I know of no way) to train a Boolean circuit to let it self-discover the ideal gates it must use to get given output sets from input sets.

The idiot savant that recognizes primes concept is interesting. Annecdotal story aside.

[kriesel]

Originally Posted by airsquirrels

The concept was that running prime95 on an exponent is essentially a black box that takes < 32 bits as its input and outputs a Boolean true or false. You could generate a theoretical Boolean circuit that performed this calculation, regardless of how infeasibly large it would be in practice. If you could find the minimal possible such circuit through brute force you would have found the best possible algorithm, even though you could not necessarily understand its methods. Although you would have to differentiate optimizing for algorithms with the shortest-longest path for speed vs generated looping circuits that may be quick small.

Isn’t a trained neural network with N nodes not so dissimilar? In this case the minimum number of nodes that could provide the correct answer may indeed be very large.

Let's try to rough size the one-clock circuit as a thought experiment. It takes a GTX1070 with its 7.2 billion transistor, 314mm2 chip 5.3 days to run CUDALucas on an 80million bit exponent, at around 1.8 Ghz (about 824 trillion clocks). Widen that out to a single clock answer, the clock gets slower because gate delays sum and the speed of light limits signaling speed across the large device. A square chip of 314mm2 area is 17.7mm on a side. Sqrt of 824 trillion is 28.7 million. I get an area of 258,000 sq km. The giant chip is a solar collector array bigger than the state of Wisconsin, by a factor of 1.52, with digital logic at 100% density. Clock rate if inversely proportional to die width is 63 Hz. If power consumption is proportional to clock rate, this consumes 0.3% of the world's average electrical generation. Transit time of a light pulse diagonally is 2.4 msec one way, 209 Hz round trip. Fabrication, siting, power and cooling are definite issues. If the general purpose design of the gpu chip is terribly space inefficient, and a purpose-specific design could fit it in one percent of the area, that's about 70% of Long Island. Then moving up from 80M to 4000M the area increases a lot, by about 2.03 power of the exponent. (4000/80) ^2.03 = 2811 times; ~continental US? Eight times world electrical output?

It's not clear how one does an LL computation fully parallel, since each iteration depends on its predecessor. The same applies to PRP3. The giant chip is scaled for all iterations. That means it would be a pipeline as deep as all iterations of an exponent. Much of the memory of a gpu is omitted if the data can be clocked through. Dividing it into roughly square pipeline stages raises the clock rate by a factor of ~9000.

Scaling it down to do one iteration of one exponent at a time gives a chip area of about 43m on a side. Still bigger than some suburban lots.

At the other extreme, teaching a device to return prime or composite for Mersenne exponents up to 2^32 is a bear, but the device is simple. A half gigabyte of memory can hold the 4-gigabit bit map, including for simplicity a bit for each of the composite exponents; a quarter gigabyte if we skip the evens. Figuring out whether to put a one indicating prime or leave a zero indicating composite takes a GTX1070 several days in the lower portion. Thirty thousand of them have a collective throughput of 4 per minute. It takes much longer in the upper portion. (Just fill it all with zeroes, and it's _mostly_ right at the start!) We think we know what to put in the first 2.5+ megabytes representing odd exponents up to about 43M, with a good degree of certainty, and nearly the first 5 megabytes with >95% confidence. It doesn't take long to write the 50 ones we know. After that, for bit positions representing prime exponents, it gets hard.

"No neural network has solved computationally difficult problems such as the n-Queens problem, the travelling salesman problem, or the problem of factoring large integers."
https://en.wikipedia.org/wiki/Artifi...retical_issues

A very simple circuit, that always returns composite, will indicate primality for mersenne numbers correctly for a very high percentage of the inputs above value 10,000. The known error rate over exponents up to a billion (~50.8 million prime exponents, 50 known Mersenne primes) is slightly under 1 ppm.

[science_man_88]

Originally Posted by kriesel

Maybe I'm missing your point, but we already know to not bother with composite exponents when looking for Mersenne Primes.
If q=ab, 2^q-1 = 2^(ab)-1 has factors 2^a-1 and 2^b-1. Consider a=3, b=5.
The binary expression is 111 111 111 111 111 (77777 octal) or 11111 11111 11111.
A special case of repdigit numbers.
Similarly you can tell the decimal numbers below are factorable at a glance:
22
333
44
5555
66666
777
8888
9999

My point was that you can use binary to find primes. Just like airsquirrels stated, because you can filter out composites.

[GP2]

Originally Posted by science_man_88

In some cases of weeding out composites, there are. For example 101101 in base 2, is divisble by 101 (aka 5). So fully repeated units( other than all of length 1) throughout is composite.

In base ten, it's well known that if the digits of a number add up to 3 or a multiple of 3, then it's divisible by 3, and the same applies to 9.

That's because if x is a factor of 10−1 then 10 ≡ 1 (mod x).

The same is true of any base, not just ten. So in octal you can use the same trick to determine if a number is divisible by 7; and in hex you can determine if a number is divisible by 3 or 5.

So just by grouping and adding up the binary digits of an arbitrary-precision number, you can determine if it's divisible by 3, 5 or 7, and obviously 2 is trivial. But I don't know if you'd save time doing that, and it certainly doesn't need neural networks to figure that out. Would neural networks really find some kind of telltale pattern in the bits that would elude mathematicians? Or maybe I misunderstood the original statement.

[airsquirrels]

Originally Posted by kriesel

Let's try to rough size the one-clock circuit as a thought experiment. It takes a GTX1070 with its 7.2 billion transistor, 314mm2 chip 5.3 days to run CUDALucas on an 80million bit exponent, at around 1.8 Ghz (about 824 trillion clocks). Widen that out to a single clock answer, the clock gets slower because gate delays sum and the speed of light limits signaling speed across the large device. A square chip of 314mm2 area is 17.7mm on a side. Sqrt of 824 trillion is 28.7 million. I get an area of 258,000 sq km. The giant chip is a solar collector array bigger than the state of Wisconsin, by a factor of 1.52, with digital logic at 100% density. Clock rate if inversely proportional to die width is 63 Hz. If power consumption is proportional to clock rate, this consumes 0.3% of the world's average electrical generation. Transit time of a light pulse diagonally is 2.4 msec one way, 209 Hz round trip. Fabrication, siting, power and cooling are definite issues. If the general purpose design of the gpu chip is terribly space inefficient, and a purpose-specific design could fit it in one percent of the area, that's about 70% of Long Island. Then moving up from 80M to 4000M the area increases a lot, by about 2.03 power of the exponent. (4000/80) ^2.03 = 2811 times; ~continental US? Eight times world electrical output?

It's not clear how one does an LL computation fully parallel, since each iteration depends on its predecessor. The same applies to PRP3. The giant chip is scaled for all iterations. That means it would be a pipeline as deep as all iterations of an exponent. Much of the memory of a gpu is omitted if the data can be clocked through. Dividing it into roughly square pipeline stages raises the clock rate by a factor of ~9000.

Scaling it down to do one iteration of one exponent at a time gives a chip area of about 43m on a side. Still bigger than some suburban lots.

At the other extreme, teaching a device to return prime or composite for Mersenne exponents up to 2^32 is a bear, but the device is simple. A half gigabyte of memory can hold the 4-gigabit bit map, including for simplicity a bit for each of the composite exponents; a quarter gigabyte if we skip the evens. Figuring out whether to put a one indicating prime or leave a zero indicating composite takes a GTX1070 several days in the lower portion. Thirty thousand of them have a collective throughput of 4 per minute. It takes much longer in the upper portion. (Just fill it all with zeroes, and it's _mostly_ right at the start!) We think we know what to put in the first 2.5+ megabytes representing odd exponents up to about 43M, with a good degree of certainty, and nearly the first 5 megabytes with >95% confidence. It doesn't take long to write the 50 ones we know. After that, for bit positions representing prime exponents, it gets hard.

"No neural network has solved computationally difficult problems such as the n-Queens problem, the travelling salesman problem, or the problem of factoring large integers."
https://en.wikipedia.org/wiki/Artifi...retical_issues

A very simple circuit, that always returns composite, will indicate primality for mersenne numbers correctly for a very high percentage of the inputs above value 10,000. The known error rate over exponents up to a billion (~50.8 million prime exponents, 50 known Mersenne primes) is slightly under 1 ppm.

That was a fun mental exercise. Please submit it to the XKCD guy so we can have fun drawings along side it!