Post Reply 
newRPL - build 1255 released! [updated to 1299]
06-21-2019, 02:58 PM (This post was last modified: 06-21-2019 03:12 PM by Claudio L..)
Post: #514
RE: newRPL - build 1255 released! [official and unofficial]
(06-21-2019 01:44 AM)The Shadow Wrote:  Claudio,

Out of curiosity, what algorithm do the NEXTPRIME and PREVPRIME commands use? I'm trying to program the prime-counting function.

That part is still incomplete but here's how it works:

* All prime numbers up to 122887 are tabulated, so working with small primes is extremely fast.
* The algorithm to test for primality looks for factors by brute force with all prime numbers up to 2^63.
* If a number has prime factors >2^63 the algorithm will (future tense) switch to either Fermat or Miller-Rabin pseudo-primality test, but no algorithm is in place as of right now (it returns that the number is prime if it can't find any prime factors < 2^63).

I still have to come back and code an algorithm for those numbers that have large prime factors (the method as-is will only fail if a number doesn't have any prime factors < 2^63, or < 18 digits long), but I figured it's not a priority since factorization of those large primes typically needs more powerful hardware anyway. But... now that newRPL runs on Android and PC, I should go back and finish the job. I'll add it to the bug tracker.
Find all posts by this user
Quote this message in a reply
Post Reply 


Messages In This Thread
RE: newRPL - build 1001 released! - pier4r - 12-16-2017, 08:03 AM
newRPL - on Hp 39gs - Martin Hepperle - 06-05-2019, 06:51 AM
RE: newRPL - build 1001 released! - pier4r - 12-23-2017, 10:16 AM
RE: newRPL - build 1001 released! - pier4r - 01-01-2018, 09:42 AM
t - Claudio L. - 01-01-2018, 03:06 PM
RE: newRPL - build 1001 released! - pier4r - 01-01-2018, 03:41 PM
RE: newRPL - build 1001 released! - pier4r - 01-02-2018, 04:54 PM
RE: newRPL - build 1001 released! - pier4r - 01-02-2018, 06:58 PM
newRPL - brickviking - 10-05-2018, 06:01 AM
RE: newRPL - build 1255 released! [official and unofficial] - Claudio L. - 06-21-2019 02:58 PM
How to participate? - erazor - 12-13-2019, 07:12 AM



User(s) browsing this thread: 2 Guest(s)