For all you Prime Factor history fans, 9999999967 proves prime in ?

[Gene]

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.

[Paul Dale]

The 34S does this ever so slightly faster


Pauli

[Jim Horn]

(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!

[Joe Horn]

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)).

[TASP]

Damn, that's spooky.

9999999967, another prime that doesn't end in '5'.

[Dieter]

(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

[Gerald H]

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?

[Claudio L.]

(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.

[Gene]

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.

[Paul Dale]

The 34S does a Miller-Rabin test. For the range of numbers it works with (0 .. 2⁶³-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

[Marcus von Cube]

(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.

[Paul Dale]

(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