For all you Prime Factor history fans, 9999999967 proves prime in ?
07-16-2016, 09:12 PM
Post: #1
 Gene Junior Moderator Posts: 831 Joined: Dec 2013
For all you Prime Factor history fans, 9999999967 proves prime in ?
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.
07-17-2016, 12:11 AM
Post: #2
 Paul Dale Senior Member Posts: 1,394 Joined: Dec 2013
RE: For all you Prime Factor history fans, 9999999967 proves prime in ?
The 34S does this ever so slightly faster

Pauli
07-17-2016, 04:19 AM
Post: #3
 Jim Horn Member Posts: 150 Joined: Dec 2013
RE: For all you Prime Factor history fans, 9999999967 proves prime in ?
(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!
07-17-2016, 06:22 AM
Post: #4
 Joe Horn Senior Member Posts: 1,333 Joined: Dec 2013
RE: For all you Prime Factor history fans, 9999999967 proves prime in ?
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)).

X<> c
-Joe-
07-17-2016, 10:17 AM
Post: #5
 TASP Senior Member Posts: 401 Joined: Mar 2015
RE: For all you Prime Factor history fans, 9999999967 proves prime in ?
Damn, that's spooky.

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

2speed HP41CX,int2XMEM+ZEN, HPIL+DEVEL, HPIL+X/IO, I/R, 82143, 82163, 82162 -25,35,45,55,65,67,70,80
07-17-2016, 03:30 PM
Post: #6
 Dieter Senior Member Posts: 2,177 Joined: Dec 2013
RE: For all you Prime Factor history fans, 9999999967 proves prime in ?
(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
07-17-2016, 04:21 PM
Post: #7
 Gerald H Senior Member Posts: 1,360 Joined: May 2014
RE: For all you Prime Factor history fans, 9999999967 proves prime in ?
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?
07-17-2016, 06:53 PM
Post: #8
 Claudio L. Senior Member Posts: 1,352 Joined: Dec 2013
RE: For all you Prime Factor history fans, 9999999967 proves prime in ?
(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.
07-17-2016, 08:48 PM
Post: #9
 Gene Junior Moderator Posts: 831 Joined: Dec 2013
RE: For all you Prime Factor history fans, 9999999967 proves prime in ?
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.
07-17-2016, 10:24 PM
Post: #10
 Paul Dale Senior Member Posts: 1,394 Joined: Dec 2013
RE: For all you Prime Factor history fans, 9999999967 proves prime in ?
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
07-22-2016, 05:02 PM
Post: #11
 Marcus von Cube Senior Member Posts: 754 Joined: Dec 2013
RE: For all you Prime Factor history fans, 9999999967 proves prime in ?
(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.

Marcus von Cube
Wehrheim, Germany
http://www.mvcsys.de
http://wp34s.sf.net
http://mvcsys.de/doc/basic-compare.html
07-23-2016, 12:27 AM
Post: #12
 Paul Dale Senior Member Posts: 1,394 Joined: Dec 2013
RE: For all you Prime Factor history fans, 9999999967 proves prime in ?
(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
 « Next Oldest | Next Newest »

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