Post Reply 
For all you Prime Factor history fans, 9999999967 proves prime in ?
07-16-2016, 09:12 PM
Post: #1
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.
Find all posts by this user
Quote this message in a reply
07-17-2016, 12:11 AM
Post: #2
RE: For all you Prime Factor history fans, 9999999967 proves prime in ?
The 34S does this ever so slightly faster Smile


Pauli
Find all posts by this user
Quote this message in a reply
07-17-2016, 04:19 AM
Post: #3
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 Smile


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!
Visit this user's website Find all posts by this user
Quote this message in a reply
07-17-2016, 06:22 AM
Post: #4
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-
Visit this user's website Find all posts by this user
Quote this message in a reply
07-17-2016, 10:17 AM
Post: #5
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
Find all posts by this user
Quote this message in a reply
07-17-2016, 03:30 PM
Post: #6
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
Find all posts by this user
Quote this message in a reply
07-17-2016, 04:21 PM
Post: #7
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?
Find all posts by this user
Quote this message in a reply
07-17-2016, 06:53 PM
Post: #8
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.
Find all posts by this user
Quote this message in a reply
07-17-2016, 08:48 PM
Post: #9
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.
Find all posts by this user
Quote this message in a reply
07-17-2016, 10:24 PM
Post: #10
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
Find all posts by this user
Quote this message in a reply
07-22-2016, 05:02 PM
Post: #11
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
Find all posts by this user
Quote this message in a reply
07-23-2016, 12:27 AM
Post: #12
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
Find all posts by this user
Quote this message in a reply
Post Reply 




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