All the extended test code I ran passed, so I'm happy that the code is working well now.
I've also switched all the precomputed inverses over to the new ones. I decided not to remove dc_divappr_q_n.c until Brian has had a chance to catch up with Windows. (I think apart from the add_333 and sub_333 functions there should be no other changes on Windows Brian.) I have merged everything into master and will wait until Brian has been able to test on Windows before removing the file dc_divappr_q_n.c, as the latter will require quite a lot of build changes on linux and Windows. Bill. On 15 April 2013 16:40, Bill Hart <[email protected]> wrote: > 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.
