WP-34S "PRIME?"



#14

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!


#15

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


#16

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

#17

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

#18

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


#19

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!

#20

And fixed in build 1125.

Integer truncation problem.


- Pauli


#21

Fantastic Bug Fix Department!

#22

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!

#23

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


#24

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


#25

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


Pauli

#26

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.


Possibly Related Threads...
Thread Author Replies Views Last Post
  [WP-34S] Unfortunate key damage with update to V3 :( svisvanatha 5 353 12-10-2013, 11:37 PM
Last Post: Les Bell
  WP-34S (Emulator Program Load/Save) Barry Mead 1 193 12-09-2013, 05:29 PM
Last Post: Marcus von Cube, Germany
  DIY HP 30b WP 34s serial flash/programming cable Richard Wahl 2 265 12-04-2013, 11:14 AM
Last Post: Barry Mead
  WP 34S/43 ?'s Richard Berler 3 290 11-10-2013, 02:27 AM
Last Post: Walter B
  My FrankenCulator (wp-34s) FORTIN Pascal 4 300 11-09-2013, 06:18 PM
Last Post: FORTIN Pascal
  WP 34S Owner's Handbook Walter B 5 441 11-09-2013, 05:34 PM
Last Post: Harald
  wp 34s overlay and programming. FORTIN Pascal 6 373 11-08-2013, 01:28 PM
Last Post: Nick_S
  m.dy in display of WP-34S Harold A Climer 3 212 11-05-2013, 11:28 AM
Last Post: Andrew Nikitin
  WP 34s : An old problem coming back Miguel Toro 2 215 11-05-2013, 03:00 AM
Last Post: Marcus von Cube, Germany
  [WP 34s] Pressure Conversion Factors Timothy Roche 8 438 11-04-2013, 07:17 PM
Last Post: Dave Shaffer (Arizona)

Forum Jump: