HP Forums

Full Version: WP-34S "PRIME?"
You're currently viewing a stripped down version of our content. View the full version with proper formatting.

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!

Apparently the maximum value for "PRIME?" is 2^31, i.e. a signed 32 bit integer. Larger primes are evaluated as composite.

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 Miller-Rabin'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^64-1 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.


- Pauli

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.


- Pauli

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? :-)

Hi, Gene,

V4N4? It's been a while(!!). The largest prime the '67 could evaluate was 10^10-33, 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!

And fixed in build 1125.

Integer truncation problem.


- Pauli

Fantastic Bug Fix Department!

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!

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...


- Pauli

Pauli, just throw a domain error if the number gets too large. Walter has to document the limits.

I'd prefer the function to work for the entire numeric range....


Pauli

263-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.