20150913, 15:46  #1  
Jan 2008
France
2^{4}×3×11 Posts 
APRCL implementations comparison
A post from Dana pushed me to time both mpz_aprcl and Pari/GP more thoroughly.
Quote:
The primes were generated using Pari/GP: Code:
setrand(2) for (i=1, 10, for (j=1, 10, a=0; until(a > 10^(i*1001)1, a=randomprime(10^(i*100))); print(a)))


20150914, 02:39  #2 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
2·11·41 Posts 
I just reran everything on my machine. The inputs are a bit different, but that shouldn't have a really big impact. I get nearly identical times for mpz_aprcl. I get substantially similar ties for djecpp. I get much faster times for Pari than I did back in early 2014 (right after 2.7.0 was released). I'm not sure why, as there is nothing substantially faster about today's HEAD vs. 2.7.0 in APRCL.
Attaching a similar spreadsheet. Sheet 1 is Idesnogu, Sheet 2 is mine. Pari has some odd timing behavior. The times for 500 digit are more than double that for 400 digit, but 600 digit is just barely more than 500. 700 is a huge jump, then 800 a small one and 900 almost no difference. I'd like to see this extended a little father. My results are mpz_aprcl faster to 500 digits, slower at 600, faster at 700 and 800, then slower at 900 and substantially slower at 1000. I'd also like to improve the speed of my ECPP implementation at the larger sizes, but that's another topic. 
20150914, 17:45  #3 
Jan 2008
France
2^{4}×3×11 Posts 
Thanks for checking. Your mpz_aprcl results are about ~20% faster than mine, while the Pari/GP ones vary from 10% slower to 60% faster, that's strange.
I need to cleanup the changes I made to mpz_aprcl, they bring me a 10%20% over mpz_aprcl1.2. What's blocking me is getting a good way to build the list of t to use (this probably requires estimating the cost of computing the Jacobi sums), which would bring mpz_aprcl closer to Pari/GP (I get the same time for one of 1000digit primes for mpz_aprcl and Pari/GP, while mpz_aprcl1.2 is 60% slower). 
20150915, 00:26  #4 
Aug 2006
5863_{10} Posts 
Did you tune your PARI? Sounds like some cutoffs are misplaced.

20150915, 00:39  #5 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
1110000110_{2} Posts 

20150915, 03:36  #6 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
1606_{8} Posts 
make clean; ./Configure tune churned away for an hour and made a tune.h file. The resulting gp produces essentially identical times.
My CPU is faster, but memory maybe a little slower (unless you don't have dual channel). That it is faster doesn't surprise me, but the differences in Pari times aren't clear. Nice to hear about your mpz_aprcl speedups. 
20150916, 07:58  #7  
Jan 2008
France
2^{4}×3×11 Posts 
Quote:
Quote:
Quote:


20150920, 23:56  #8  
Mar 2006
111011000_{2} Posts 
Quote:
Also, I once had some code to generate t values. However, once I incorporated Jason Moxam's Jacobi sums, I was locked in to that particular set of t values. I started writing code to generate new Jacobi sums based on a different set of t values, but was getting decent performance with the original set, so never really finished it. If you're interested, I can pick that back up and try to finish it so that we can test different sets of t values. 

20150923, 13:02  #9  
Jan 2008
France
2^{4}×3×11 Posts 
Quote:
Quote:
What I miss is a way to select a good value. This is dependent on the underlying hardware, libraries and APRCL implementation performance. Pari/GP is slightly better here, but not perfect (which explains why it loses sometimes against mpz_aprcl). It looks like FLINT APRCL is even faster for some of the ranges (I'll post results later). I also guess these various implementations offer various optimizations missing in the others. 

20150923, 13:53  #10 
Jan 2008
France
528_{10} Posts 
Here are corrected results plus new FLINT APRCL results.
The FLINT implementation is always faster than both mpz_aprcl and Pari/GP. 
20151028, 00:36  #11 
"Vladimir Glazachev"
Oct 2015
Russia, SaintPetersburg
1 Posts 
Hi!
I worked on the implementation of APRCL in FLINT this summer during GSoC2015. I wrote some blogposts, so maybe someone find it useful  link. My code is still not merged with FLINT, so that it is not checked very carefully. Also I have ideas what can be done to speed up. Thanks for your timings, thats interesting. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Comparison of NFS tools  CRGreathouse  Factoring  3  20180205 14:55 
Any CIDE Primality Test Implementations?  Stargate38  Computer Science & Computational Number Theory  4  20141102 19:25 
Comparison Page Not Working  wblipp  Operation Billion Digits  0  20121124 06:33 
PFGW vs LLR comparison discussion  henryzz  Conjectures 'R Us  37  20100219 07:42 
Pollard's Algorithm & That of Devaraja comparison  devarajkandadai  Miscellaneous Math  22  20050610 11:13 