search

TPU-Mersenne-Prime-Search / TensorPrime

Mersenne primality test for the Tensor Processing Unit (TPU)
GNU General Public License v3.0
5 stars 4 forks source link

[BUG] TensorFlow Implementation: Some Numbers Show As Composite When They Are Prime (on CPU, maybe TPU also) #27

Closed Danc2050 closed 2 years ago

Danc2050 commented 2 years ago

Daniel's Post

After running the TimeTrials.ipynb benchmark, some numbers are showing up as Composite when run on the CPU notebook, even though they are prime. I am not sure if this is also on a TPU, I am testing this now. Here are the results and the full output file: CPUVersion.txt

2 tested in 0.16403603553771973 sec: composite
3 tested in 0.0206449031829834 sec: composite
19937 tested in 4381.768760204315 sec: composite
21701 tested in 5119.884444952011 sec: composite
23209 tested in 5771.275307416916 sec: composite

@tdulcet posted what he believes the issue may be for 3. It is possible that the issue expands up into higher numbers, as seen above. Here is Teal's fix for 3 and possibly the above:

Teal's Post

I do not believe 2²-1 is possible to PRP test, but 2³-1 should work. This issue is this line: https://github.com/TPU-Mersenne-Prime-Search/TensorPrime/blob/a86883bc48e52da7d3584d9420985cda5553fcc5/prptest.py#L14-L15 For type 3 residues it would be s == 9 % n as I did in my original PRP example programs (or more precisely s == (a * a) % n, where a is the PRP base), although they should of course use type 1 residues by default...

Originally posted by @tdulcet in https://github.com/TPU-Mersenne-Prime-Search/TensorPrime/issues/24#issuecomment-1044303207

tdulcet commented 2 years ago

It is possible that the issue expands up into higher numbers, as seen above.

The issue with higher numbers is likely a round off error (ROE), as it needs to use a higher FFT length, although it could of course also be a bug in their program. Adding ROE checking and GEC would be a good start to identify the problem, as would outputting the interim residues in hexadecimal format to compare with those from the existing GIMPS programs...

willfarris commented 2 years ago

As Teal mentioned, this was almost certainly due to the ROE issues we've discussed. As far as we can tell all prime numbers which can be tested by our program now test as "probably prime" in the latest master.