mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Software

Reply
 
Thread Tools
Old 2015-09-08, 14:50   #1
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2·2,969 Posts
Default ECPP on Windows?

I occasionally use a Windows machine. What software is available for primality proving? I used to use Primo but the Windows version is no longer available.
CRGreathouse is offline   Reply With Quote
Old 2015-09-08, 15:10   #2
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

100111110101012 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
I occasionally use a Windows machine. What software is available for primality proving? I used to use Primo but the Windows version is no longer available.
Not ECPP but APRT-CL is what Pari/gp uses for primality proving and the latter is certainly available on Windows.
xilman is offline   Reply With Quote
Old 2015-09-08, 21:59   #3
WraithX
 
WraithX's Avatar
 
Mar 2006

23·59 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
I occasionally use a Windows machine. What software is available for primality proving? I used to use Primo but the Windows version is no longer available.
I have written an APRCL code base that is easy to integrate into other projects. You can see a thread about it here:
http://www.mersenneforum.org/showthread.php?t=18353

Also, danaj has written an ECPP prime prover, called ECPP-DJ. You can find a thread about that here:
http://www.mersenneforum.org/showthread.php?t=18283

In danaj's thread you can see some comparisons he made of how fast different prime proving programs are. The most recent one I saw was in post #30 here:
http://www.mersenneforum.org/showpos...1&postcount=30
WraithX is offline   Reply With Quote
Old 2015-09-09, 05:01   #4
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

2·3·151 Posts
Default

WraithX's mpz_aprcl is easy to use. It's faster than my ECPP for larger sizes, and a bit faster than Pari at all sizes in my testing. No certificate of course. A new APR-CL implementation was just put in a pull request for FLINT, but I have no experience with it.

My ECPP creates certificates and includes a verifier for its format and Primo. I still have not made changes to output Primo certificates (Marcel gave me enough info that I think I can do it, but just haven't found the time).

If you get the larger poly sets it should work pretty well up to ~2000 digits, but I really haven't done testing past that. It definitely is losing out to Primo as the size gets larger. Single thread only.

If you get Strawberry Perl for your Windows machine, it is included in the included ntheory Perl module. No standalone program and uses very small polynomial sets. Still works well up to 500 digits. It gives you GMP, gcc, and dmake so you can easily compile whatever you need yourself.


Other ECPP options I'm aware of:
  • Primo. We know it and love it, but not open source and no Windows option.
  • Morain's ECPP. Very old (2001). Decent performance up to 300ish digits. If I recall correctly from my tests two years ago, it uses more n-1 and n+1 effort so sometimes ran quickly for some values in that range, at the expense of speed for larger inputs. At 1000 digits it was >40x slower than my ECPP or WraithX's APR-CL. It writes certificates, but you'd have to write your own parser and verifier (or something to convert to my or Primo's format). Linux binary only so no help with Windows.
  • GMP-ECPP. Nice start, but not very practical for >100 digits. It's written following Cohen (which is the base for mine as well though I've veered off a little). Creates its own polynomials, which is very slow and has some bugs, so the time skyrockets once past 200 or so digits, often taking 1-2 days to prove 500-700 digit numbers. I wrote a Perl script to convert its progress output into a certificate that works in my verifier.
  • Sage has a rudimentary ECPP implementation written in 2010, but I don't think it ever got merged into the main branch. I wrote a script to turn its certificates into my format so they can be verified. I didn't run any performance tests on it. The factoring portion is trial division so I wouldn't expect it to work well as sizes increase.

Last fiddled with by danaj on 2015-09-09 at 05:02
danaj is offline   Reply With Quote
Old 2015-09-09, 07:29   #5
schickel
 
schickel's Avatar
 
"Frank <^>"
Dec 2004
CDP Janesville

2·1,049 Posts
Default

For another option, consider a VM+Primo solution. My rig is an AMD Phenom II x6 running at a stock clock of 3.2 GHz, Win 7 Pro, 8 GB RAM. I've got VirtualBox installed running the second-to-latest Ubuntu configured with a 30GB HDD, 8 GB Ram, and 6-cores.

Surprisingly, the performance is not very crippled. A single threaded run of the last available Windows version for 2^6641-511 resulted in this:
Code:
[Running Times]
Initialization=1.59s
1stPhase=3h 3mn 44s
2ndPhase=49mn 11s
Total=3h 52mn 57s
So about 4 hours for 2000 digits single-threaded.

(I'll post the Linux times in the next message....)

Last fiddled with by schickel on 2015-09-09 at 07:30 Reason: damn fingers!
schickel is offline   Reply With Quote
Old 2015-09-09, 07:43   #6
schickel
 
schickel's Avatar
 
"Frank <^>"
Dec 2004
CDP Janesville

2×1,049 Posts
Default

For the Linux version, here are the results (I had to go to 2000 digits to make it worth comparing):

Single thread (while the Windows version was running on the desktop!):
Code:
[Running Times (Wall-Clock)]
1stPhase=2963s
2ndPhase=660s
Total=3623s

[Running Times (Processes)]
1stPhase=2957s
2ndPhase=681s
Total=3639s
So, about an hour....

For 3 threads:
Code:
[Running Times (Wall-Clock)]
1stPhase=1126s
2ndPhase=228s
Total=1353s

[Running Times (Processes)]
1stPhase=3273s
2ndPhase=686s
Total=3959s
So, less than 1/2 the wall time, but a little more process time, actually.....

And finally, with the full 6 threads available:
Code:
[Running Times (Wall-Clock)]
1stPhase=615s
2ndPhase=115s
Total=730s

[Running Times (Processes)]
1stPhase=3333s
2ndPhase=674s
Total=4007s
So again, 1/2 the wall time, with more actual processing time, since it spends more time testing determinants at each step, but still blowing the Windows version completely out of the water.

I find that I can run a quick clearing run of <1000 digits with the Windows version, but going above that, I tend to use the Linux version exclusively. In fact, I'm working on a 10,1410-digit monster right now that's about 1/2 done. Unfortunately, the summer heat makes it only 2 or 3 cores during the day
schickel is offline   Reply With Quote
Old 2015-09-09, 18:43   #7
ldesnogu
 
ldesnogu's Avatar
 
Jan 2008
France

3·179 Posts
Default

Quote:
Originally Posted by danaj View Post
WraithX's mpz_aprcl is easy to use. It's faster than my ECPP for larger sizes, and a bit faster than Pari at all sizes in my testing.
Are you sure? On my Haswell 4770K, it seems Pari/GP is faster than mpz_aprcl (very recent checkouts of both Pari and gmp) starting between 500 and 600 digits.

As an example the 601 digit numbers 10...0543 is tested in 22.7s by Pari/GP and in 32.2s by mpz_aprcl 1.2.

Note I have some local modifications to mpz_aprcl that make it ~10% faster than mpz_aprcl 1.2, but that's far from enough to catch up with Pari/GP.
ldesnogu is online now   Reply With Quote
Old 2015-09-09, 19:13   #8
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

350210 Posts
Default

Quote:
Originally Posted by schickel View Post
In fact, I'm working on a 10,1410-digit monster right now that's about 1/2 done.
Is that really decimal digits or binary?
paulunderwood is offline   Reply With Quote
Old 2015-09-09, 21:49   #9
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

2·3·151 Posts
Default

Quote:
Originally Posted by ldesnogu View Post
Are you sure? On my Haswell 4770K, it seems Pari/GP is faster than mpz_aprcl (very recent checkouts of both Pari and gmp) starting between 500 and 600 digits.

As an example the 601 digit numbers 10...0543 is tested in 22.7s by Pari/GP and in 32.2s by mpz_aprcl 1.2.

Note I have some local modifications to mpz_aprcl that make it ~10% faster than mpz_aprcl 1.2, but that's far from enough to catch up with Pari/GP.
It was testing on an otherwise idle 4.3GHz 4770K running Linux, using Pari 2.7.0 and mpz_aprcl 1.1, At those sizes averaging 5 random n-digit primes. At 500 digits Pari was 20.8s, mpz_aprcl 13.3s. At 600 digits, Pari 35.4s, mpz_aprcl 27.8s. My spreadsheet shows no size where Pari came out faster, so it wasn't just a lucky few numbers. At 2000 digits it was 5039s for Pari, 4374s for mpz_aprcl.

GMP 6.0.0a made a big difference, but you have recent versions. I did the timing in May 2014.
danaj is offline   Reply With Quote
Old 2015-09-10, 00:20   #10
schickel
 
schickel's Avatar
 
"Frank <^>"
Dec 2004
CDP Janesville

2·1,049 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
Is that really decimal digits or binary?
Damn fingers again....it's actually 10,141 digits. That's what I get for posting on a different machine.
schickel is offline   Reply With Quote
Old 2015-09-14, 12:32   #11
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

90610 Posts
Default

I retested with Pari 2.8.0 HEAD. My results for mpz_aprcl 1.2 and dj-ecpp are essentially the same, but all my Pari results are faster. I don't think this is a 2.7.0 vs. 2.8.0 difference. I need to extend the results out past 1000 digits, but it's certainly more competitive, and is definitely faster than mpz_aprcl and dj-ecpp at 900 and 1000 digits.


Details on this thread.

Thanks Idesnogu, for pointing this out.

Last fiddled with by danaj on 2015-09-14 at 12:33
danaj is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
ECPP-DJ danaj Computer Science & Computational Number Theory 59 2020-10-10 04:57
New ECPP record mjm Computer Science & Computational Number Theory 33 2020-02-13 14:50
Can I just leave this here? (ECPP) trhabib Miscellaneous Math 6 2011-08-19 16:34
Fast ECPP T.Rex Math 6 2007-06-25 16:42
new ECPP article R. Gerbicz GMP-ECM 2 2006-09-13 16:24

All times are UTC. The time now is 08:29.

Sun Nov 29 08:29:30 UTC 2020 up 80 days, 5:40, 3 users, load averages: 1.30, 1.35, 1.30

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.