The Museum of HP Calculators

HP Forum Archive 20

[ Return to Index | Top of Index ]

WP-34S "PRIME?"
Message #1 Posted by Jim Horn on 16 June 2011, 6:44 p.m.

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!

      
Re: WP-34S "PRIME?"
Message #2 Posted by Jim Horn on 16 June 2011, 6:49 p.m.,
in response to message #1 by Jim Horn

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

            
Re: WP-34S "PRIME?"
Message #3 Posted by Paul Dale on 16 June 2011, 6:59 p.m.,
in response to message #2 by Jim Horn

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

      
Re: WP-34S "PRIME?"
Message #4 Posted by Paul Dale on 16 June 2011, 6:58 p.m.,
in response to message #1 by Jim Horn

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

      
Re: WP-34S "PRIME?"
Message #5 Posted by gene wright on 16 June 2011, 10:17 p.m.,
in response to message #1 by Jim Horn

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

            
Re: WP-34S "PRIME?"
Message #6 Posted by Jim Horn on 16 June 2011, 10:29 p.m.,
in response to message #5 by gene wright

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!

      
Re: WP-34S "PRIME?"
Message #7 Posted by Paul Dale on 16 June 2011, 10:43 p.m.,
in response to message #1 by Jim Horn

And fixed in build 1125.

Integer truncation problem.

- Pauli

            
Re: WP-34S "PRIME?"
Message #8 Posted by Gerson W. Barbosa on 16 June 2011, 11:10 p.m.,
in response to message #7 by Paul Dale

Fantastic Bug Fix Department!

            
Re: WP-34S "PRIME?"
Message #9 Posted by Jim Horn on 16 June 2011, 11:33 p.m.,
in response to message #7 by Paul Dale

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!

      
Re: WP-34S "PRIME?"
Message #10 Posted by Paul Dale on 17 June 2011, 3:53 a.m.,
in response to message #1 by Jim Horn

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

            
Re: WP-34S "PRIME?"
Message #11 Posted by Marcus von Cube, Germany on 17 June 2011, 4:01 a.m.,
in response to message #10 by Paul Dale

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

                  
Re: WP-34S "PRIME?"
Message #12 Posted by Paul Dale on 17 June 2011, 5:55 a.m.,
in response to message #11 by Marcus von Cube, Germany

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

Pauli

            
Re: WP-34S "PRIME?"
Message #13 Posted by Paul Dale on 17 June 2011, 6:06 a.m.,
in response to message #10 by Paul Dale

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.


[ Return to Index | Top of Index ]

Go back to the main exhibit hall