ECPP on Windows?

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

[xilman]

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.

[WraithX]

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:
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

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

[schickel]

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:

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

[schickel]

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!):

[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:

[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:

[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

[ldesnogu]

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.

[paulunderwood]

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?

[danaj]

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.

[schickel]

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.

[danaj]

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.