Hi all, I've finally managed to get the divide and conquer integer division code I've been working on into MPIR. The test code is now passing, though I will need to do some more testing.
Below are timings for divapprox code in GMP and the new code. I've included the best timings out of basecase and divide and conquer in each case; new code DIVAPPR size = 3: classical = 5.7e-08s, size = 4: classical = 7.5e-08s, size = 5: classical = 9.7e-08s, size = 6: classical = 1.17e-07s, size = 7: classical = 1.41e-07s, size = 8: classical = 1.65e-07s, size = 9: classical = 1.89e-07s, size = 10: classical = 2.14e-07s, size = 11: classical = 2.38e-07s, size = 13: classical = 2.92e-07s, size = 15: classical = 3.64e-07s, size = 17: classical = 4.28e-07s, size = 19: classical = 4.89e-07s, size = 21: classical = 5.96e-07s, size = 24: classical = 7.25e-07s, size = 27: classical = 8.7e-07s, size = 30: classical = 1.043e-06s, size = 33: classical = 1.2e-06s, size = 37: classical = 1.475e-06s, size = 41: classical = 1.8e-06s, size = 46: divconquer = 2.14e-06s size = 51: divconquer = 2.59e-06s size = 57: divconquer = 3.1e-06s size = 63: divconquer = 3.77e-06s size = 70: divconquer = 4.46e-06s size = 77: divconquer = 5.19e-06s size = 85: divconquer = 6.06e-06s size = 94: divconquer = 6.89e-06s size = 104: divconquer = 8.2e-06s size = 115: divconquer = 9.6e-06s size = 127: divconquer = 1.16e-05s size = 140: divconquer = 1.36e-05s size = 154: divconquer = 1.57e-05s size = 170: divconquer = 1.83e-05s size = 188: divconquer = 2.11e-05s size = 207: divconquer = 2.5e-05s size = 228: divconquer = 2.9e-05s size = 251: divconquer = 3.47e-05s size = 277: divconquer = 4.09e-05s size = 305: divconquer = 4.69e-05s size = 336: divconquer = 5.63e-05s size = 370: divconquer = 6.24e-05s size = 407: divconquer = 7.4e-05s size = 448: divconquer = 8.6e-05s size = 493: divconquer = 0.000103s size = 543: divconquer = 0.000121s size = 598: divconquer = 0.000142s size = 658: divconquer = 0.000164s size = 724: divconquer = 0.000185s size = 797: divconquer = 0.000221s size = 877: divconquer = 0.000253s size = 965: divconquer = 0.000294s gmp-5.1.1 DIVAPPR size = 3: classical = 6.7e-08s, size = 4: classical = 8.8e-08s, size = 5: classical = 1.13e-07s, size = 6: classical = 1.36e-07s, size = 7: classical = 1.85e-07s, size = 8: classical = 1.95e-07s, size = 9: classical = 2.27e-07s, size = 10: classical = 2.51e-07s, size = 11: classical = 2.98e-07s, size = 13: classical = 3.54e-07s, size = 15: classical = 4.35e-07s, size = 17: classical = 5.07e-07s, size = 19: classical = 6.07e-07s, size = 21: classical = 7.05e-07s, size = 24: classical = 8.35e-07s, size = 27: classical = 1.052e-06s, size = 30: classical = 1.233e-06s, size = 33: classical = 1.447e-06s, size = 37: classical = 1.719e-06s, size = 41: classical = 2e-06s, size = 46: classical = 2.4e-06s, size = 51: classical = 2.81e-06s, size = 57: classical = 3.38e-06s, size = 63: classical = 3.97e-06s, size = 70: classical = 4.67e-06s, size = 77: classical = 5.45e-06s, size = 85: classical = 6.38e-06s, size = 94: classical = 7.48e-06s, size = 104: classical = 8.9e-06s, size = 115: classical = 1.04e-05s, size = 127: classical = 1.25e-05s, size = 140: classical = 1.46e-05s, size = 154: classical = 1.72e-05s, size = 170: classical = 2.05e-05s, size = 188: classical = 2.43e-05s, size = 207: classical = 2.9e-05s, size = 228: classical = 3.45e-05s, size = 251: divconquer = 4.07e-05s size = 277: divconquer = 4.8e-05s size = 305: divconquer = 5.6e-05s size = 336: divconquer = 6.47e-05s size = 370: divconquer = 7.63e-05s size = 407: divconquer = 9e-05s size = 448: divconquer = 0.000104s size = 493: divconquer = 0.000123s size = 543: divconquer = 0.000143s size = 598: divconquer = 0.000166s size = 658: divconquer = 0.000193s size = 724: divconquer = 0.000224s size = 797: divconquer = 0.000265s size = 877: divconquer = 0.000305s size = 965: divconquer = 0.000358s So it looks like the new code is most often about 20% faster than GMP. The main things that remain to be done now are: * further testing * switch all precomputed inverses in MPIR over to the new ones (actually test code passes either way because the precomputed inverses are rarely different, but we have to change them obviously) * remove the file mpn/generic/dc_divappr_q_n.c which I believe is no longer needed * write speed and tuning code for the new cutoffs (they are currently hard coded) Once I've done the first three I'll merge into trunk. They may or may not take a while to do depending on how the testing goes. I plan to work on a new release of MPIR after May 12th (I am running a flint workshop from 4-12 May). We have a long list of bugs and tickets which need to be resolved, many of which have been reported by the Sage project. Bill. -- You received this message because you are subscribed to the Google Groups "mpir-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. Visit this group at http://groups.google.com/group/mpir-devel?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
