+- HP Forums (https://www.hpmuseum.org/forum)
+-- Forum: Not HP Calculators (/forum-7.html)
+--- Forum: Not quite HP Calculators - but related (/forum-8.html)
+--- Thread: For all you Prime Factor history fans, 9999999967 proves prime in ? (/thread-6567.html)
For all you Prime Factor history fans, 9999999967 proves prime in ? - Gene - 07-16-2016 09:12 PM
The number 9,999,999,967 is the largest 10 digit prime number. Early PPC history buffs will remember the numerous Prime Factor programs that used this as the longest test case to prove prime on a 10 digit value.
For Jim Horn's Speedy Factor finder program from PPCJ V5N2P22, this test value proved prime in 2 hours 55 min.
Thought I would post the result from the PFCT function in mcode from the SandMath 4x4 rom running at TURBO 50 on my 41CL.
9,999,999,967 proves prime in about 9.95 seconds.
How times have changed. Well done Jim in paving the way. Well done Angel with all your mcode work.
RE: For all you Prime Factor history fans, 9999999967 proves prime in ? - Paul Dale - 07-17-2016 12:11 AM
The 34S does this ever so slightly faster
Pauli
RE: For all you Prime Factor history fans, 9999999967 proves prime in ? - Jim Horn - 07-17-2016 04:19 AM
(07-17-2016 12:11 AM)Paul Dale Wrote: The 34S does this ever so slightly faster
Pauli
Your understatement is only excelled by the excellent performance of the WP34S! As the "Speedy Factor Finder" author back in the Cretaceous era, I've been delighted by the improved speed of newer machines than my much-loved HP67. But yours blows away all others out of the box. And handles far larger values at that! Bravissimo! Ausgezeichnet! And many sincere thanks!
RE: For all you Prime Factor history fans, 9999999967 proves prime in ? - Joe Horn - 07-17-2016 06:22 AM
The suspense is killing me... Ok, so how fast does the 34S do it? FWIW, the HP Prime hardware returns approximately 0.0072 seconds for the CAS command time(isprime(9999999967)).
RE: For all you Prime Factor history fans, 9999999967 proves prime in ? - TASP - 07-17-2016 10:17 AM
Damn, that's spooky.
9999999967, another prime that doesn't end in '5'.
RE: For all you Prime Factor history fans, 9999999967 proves prime in ? - Dieter - 07-17-2016 03:30 PM
(07-17-2016 06:22 AM)Joe Horn Wrote: The suspense is killing me... Ok, so how fast does the 34S do it?
On my hardware 34s the PRIME? test returns "true" in about half a second.
Dieter
RE: For all you Prime Factor history fans, 9999999967 proves prime in ? - Gerald H - 07-17-2016 04:21 PM
One should perhaps mention that both the Prime & the WP 34S don't use division up to the square root of the factoree....or do they?
RE: For all you Prime Factor history fans, 9999999967 proves prime in ? - Claudio L. - 07-17-2016 06:53 PM
(07-17-2016 06:22 AM)Joe Horn Wrote: The suspense is killing me... Ok, so how fast does the 34S do it? FWIW, the HP Prime hardware returns approximately 0.0072 seconds for the CAS command time(isprime(9999999967)).
To quench your thirst for results, here's another one:
newRPL does it in 0.057s, but it doesn't use any advanced algorithm (yet). This is plain brute force: take every prime from 1 to sqrt(N), divide it and check the remainder. I wouldn't be surprised if a more advanced primality test in the 34S would beat it.
RE: For all you Prime Factor history fans, 9999999967 proves prime in ? - Gene - 07-17-2016 08:48 PM
Good all. The PFCT command in the 41CL Sandmath module DOES do a factoring approach. Try 9999999968 and you'll get a list of factors.
I do love and appreciate the 34S :-) but the 41CL is still a 41c in my mind, even with the new CPU...so it dates to 1979 in my heart. haha.
RE: For all you Prime Factor history fans, 9999999967 proves prime in ? - Paul Dale - 07-17-2016 10:24 PM
The 34S does a Miller-Rabin test. For the range of numbers it works with (0 .. 263-1), the test should be exact.
The performance isn't ideal. The big number arithmetic was written to be small not fast. This could be improved several orders of magnitude without too much effort.
Pauli
RE: For all you Prime Factor history fans, 9999999967 proves prime in ? - Marcus von Cube - 07-22-2016 05:02 PM
(07-17-2016 10:24 PM)Paul Dale Wrote: The performance isn't ideal. The big number arithmetic was written to be small not fast. This could be improved several orders of magnitude without too much effort.
I doubt it. The code is already written for integer mode, even if called from decimal mode.
RE: For all you Prime Factor history fans, 9999999967 proves prime in ? - Paul Dale - 07-23-2016 12:27 AM
(07-22-2016 05:02 PM)Marcus von Cube Wrote: I doubt it. The code is already written for integer mode, even if called from decimal mode.
Yes, it always collapses to the integer code, however I'm using naïve algorithms for both modular multiplication and modular exponentiation. They are in no way optimised for performance. Both of these use a test bit and shift algorithm which will be very slow. There is plenty of scope for improvement.
Pauli