Post Reply 
[HP35s] Program for prime number (Wheel Sieve and Miller-Rabin)
04-09-2019, 03:52 PM (This post was last modified: 04-10-2019 07:31 AM by fred_76.)
Post: #46
RE: [HP35s] Program for prime number (brut force)
Hi !

After a long period without programming I was finally able to complete the Miller-Rabin primality test on the HP35s. It runs very fast, even if the code is not optimized, but from 9 digits numbers and above. For numbers less than 9 digits, the optimized brut force is faster. For numbers above 11 digits, I still have problems to calculate the exponentiation without overflow therefore I can't conclude.

Compared to the "brut force V3" :


Quote:Run time
8 digits 99 999 989 1m 28s => 2m 09s (1.5x slower)
9 digits 999 999 937 4m 36s => 2m 14s (2.1x faster)
10 digits 9 999 999 967 14m 37s => 2m 39s (5.5x faster)
11 digits 99 999 999 977 46m 26s => 2m 57s (15.8x faster)
11.7 digits 500 000 000 023 => 3m 02s
12 digits 999 999 999 989 2h 32m 18s => not working
(2^249999999997 mod 999999999989 does not work well because numbers are too big, I shall change the algorithm)
Find all posts by this user
Quote this message in a reply
Post Reply 


Messages In This Thread
RE: [HP35s] Program for prime number (brut force) - fred_76 - 04-09-2019 03:52 PM



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