mersenneforum.org ECPP on Windows?
 Register FAQ Search Today's Posts Mark Forums Read

 2015-09-08, 14:50 #1 CRGreathouse     Aug 2006 11×13×41 Posts 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.
2015-09-08, 15:10   #2
xilman
Bamboozled!

May 2003
Down not across

5·19·107 Posts

Quote:
 Originally Posted by CRGreathouse 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.

2015-09-08, 21:59   #3
WraithX

Mar 2006

23×59 Posts

Quote:
 Originally Posted by CRGreathouse 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:

Also, danaj has written an ECPP prime prover, called ECPP-DJ. You can find a thread about that here:

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

 2015-09-09, 05:01 #4 danaj   "Dana Jacobsen" Feb 2011 Bangkok, TH 38616 Posts 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
 2015-09-09, 07:29 #5 schickel     "Frank <^>" Dec 2004 CDP Janesville 2×1,061 Posts 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!
 2015-09-09, 07:43 #6 schickel     "Frank <^>" Dec 2004 CDP Janesville 2×1,061 Posts 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
2015-09-09, 18:43   #7
ldesnogu

Jan 2008
France

10208 Posts

Quote:
 Originally Posted by danaj 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.

2015-09-09, 19:13   #8
paulunderwood

Sep 2002
Database er0rr

3×11×101 Posts

Quote:
 Originally Posted by schickel 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?

2015-09-09, 21:49   #9
danaj

"Dana Jacobsen"
Feb 2011
Bangkok, TH

11100001102 Posts

Quote:
 Originally Posted by ldesnogu 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.

2015-09-10, 00:20   #10
schickel

"Frank <^>"
Dec 2004
CDP Janesville

2×1,061 Posts

Quote:
 Originally Posted by paulunderwood 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.

 2015-09-14, 12:32 #11 danaj   "Dana Jacobsen" Feb 2011 Bangkok, TH 2×11×41 Posts 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

 Similar Threads Thread Thread Starter Forum Replies Last Post mjm Computer Science & Computational Number Theory 33 2020-02-13 14:50 danaj Computer Science & Computational Number Theory 58 2018-02-06 21:52 trhabib Miscellaneous Math 6 2011-08-19 16:34 T.Rex Math 6 2007-06-25 16:42 R. Gerbicz GMP-ECM 2 2006-09-13 16:24

All times are UTC. The time now is 09:33.

Sat Aug 8 09:33:04 UTC 2020 up 22 days, 5:19, 1 user, load averages: 1.95, 2.08, 2.07