With build #1108 I noticed that 9999999967 "PRIME?" returns false. Is there a limit to the values for which PRIME? works correctly?
Many thanks to the team for this *remarkable* calculator  I'm really enjoying it!
WP34S "PRIME?"

06162011, 06:44 PM
With build #1108 I noticed that 9999999967 "PRIME?" returns false. Is there a limit to the values for which PRIME? works correctly? Many thanks to the team for this *remarkable* calculator  I'm really enjoying it!
06162011, 06:49 PM
Apparently the maximum value for "PRIME?" is 2^31, i.e. a signed 32 bit integer. Larger primes are evaluated as composite.
06162011, 06:58 PM
We honestly don't know for sure what the smallest value the primality test fails for. We believe that no composite number should ever be declared a prime by this function. The test is MillerRabin's using the first fifteen prime numbers as a base. There is a proof that 7 or 8 are sufficient for a fairly large number (who exact value escapes me) which is less than the largest integer we allow (2^641 in integer mode, quite a bit less for reals). For more bases like we use, there are conjectures that no composite number will be declared prime for values well in excess of the largest exact integer we can handle. I didn't think the converse could occur (declaring a prime composite) so I'll have a look & try to see what's going on.
06162011, 06:59 PM
Hmmm, seems like you found a bug.... My goal is for PRIME? to work for all values with a high degree of confidence. I.e. the conjectured accuracy rather than the proven level.
06162011, 10:17 PM
Hey Jim. Still using that 10 digit prime? I bet the 34s will prove it prime a lot faster than the HP 65, HP 25, and HP 67 prime factor programs from the PPC Journal, dont' you think? :)
06162011, 10:29 PM
Hi, Gene, V4N4? It's been a while(!!). The largest prime the '67 could evaluate was 10^1033, i.e. 9999999967. The first eight digits are obvious; the last two are strangely easy to remember considering how many hours I spent diving into mine! I used Wolfram Alpha to try values above and below expected powers of two to find what I reported above. NextPrime[2^31,1] there evaluates as prime on the '34S; NextPrime[2^31,1] does not. Of course, the newer algorithms are *so* much more powerful than MOD30 trial division. Again, my sincere thanks and admiriation to the '34S team!
06162011, 10:43 PM
And fixed in build 1125. Integer truncation problem.
06162011, 11:10 PM
Fantastic Bug Fix Department!
06162011, 11:33 PM
Fantastic indeed! I ran a test of the last 10 primes below 2^31 on the errant version; all showed as "true". The first 10 above it gave three "true" and seven "false" outputs. All of which is moot. I'll flog it some tomorrow when I get to work (where the programming cable is  thanks Gene!) but my hat is off again to Pauli's incredibly quick and fine corrections. Meanwhile, thank you for the chance to study your code and learn from it  it's marvelous!
06172011, 03:53 AM
Seems to be working for number up to 2^63 e.g. the largest prime less than this is 9223372036854775783 which tests as prime. The largest prime less than 2^64 is testing as composite :( I'm not sure there is much I can easily do about this since we are likely hitting integer size limits. I'll have a quick look tomorrow if I remember. This is much larger than the largest integer that can be represented exactly in real mode...
06172011, 04:01 AM
Pauli, just throw a domain error if the number gets too large. Walter has to document the limits.
06172011, 05:55 AM
I'd prefer the function to work for the entire numeric range....
06172011, 06:06 AM
2^{63}1 is the limit here :( So prime numbers equal to or greater than 9,223,372,036,854,775,837 will not necessarily return true from PRIME? Likewise composite numbers greater than 9,223,372,036,854,775,808 may return false (although this is less likely I suspect). Below these values the results should be accurate. This limit only applies in integer mode with unsigned 64 bit word size. For all other modes and word sizes, it isn't a limitation. The code relies on one bit beyond the largest value being available during the calculation and I'm not bothered to work around this (mostly because it will be fairly involved and partly because we're handling pretty large numbers already). Walter, can you please document this limitation :)  Pauli
Edited: 17 June 2011, 6:08 a.m. 
« Next Oldest  Next Newest »
