The figures you provide are very interesting. Though they illustrate something interesting. None of the packages which use GMP/MPIR actually use the code therein for binomial coefficients. They all have their own code. I suspect this sort of thing happens because a majority of those packages are built on top of the mpn layer of GMP/MPIR not the mpz layer. So this bothers me a little.
Would such code be suitable for the mpn layer of MPIR? Maybe, but only if that layer was considerably expanded from its current state. The current major pushes in MPIR development are: * Faster assembly code on a variety of platforms * Optimising Toom 4 and Toom 7 multiplication * Optimising the FFT * Faster division code (esp. division by part of a limb, 1 limb or 2 limbs and asymptotically fast algorithms) * Faster XGCD code (making use of the asymptotically fast code Niel's Mohler developed for GCD, which is now a part of MPIR) * Supporting more platforms * Rewriting the build system in python * Support for parallel processing (e.g. multithreaded code) and GPU's * Writing a new mpir_n layer (similar to mpn, but more robust) * A few other things that some of us have been discussing You can see that there's a lot to be done before we have things fleshed out enough to be including mpn implementations of root testing and binomial computations. And my worry is that, whilst it will be a nice recognition of your work to have it included in MPIR, it won't be getting used as much as it should. My feeling, looking through your code is that: * It really sits *on top of* the mpz layer * It relies on some code for single limbs that is not abstracted anywhere in MPIR, but should be It should: * be implemented *in* the new mpir_n layer * the unsigned long portion should be abstracted out into a new long layer (just as there is a longlong.h, there should be a long.c and long.h) I suspect that we'll include some version of your code now at the mpz layer, just because we can, and it's significantly faster than what we have. But I'd also be interested to know, have you ever written anything for the mpn layer, and would you be interested in working on some code at that level, to help us towards our goals there. We currently have a shortage of good people working at the C level in MPIR. Bill. P.S: if you have more code of the kind you've submitted, there's also my project FLINT (http://www.flintlib.org). I *certainly* want to include your code in that. That is used by Sage for example, and *WILL* get used. 2009/4/27 gerrob <robert.gerb...@gmail.com>: > > On ápr. 27, 03:22, Bill Hart <goodwillh...@googlemail.com> wrote: >> Did you receive any feedback >> on the code from them? > > As I remember at the same time there were 4 codes from 3 peoples to > speed up the > computation of binomial coefficients. What hasn't been done is to > choose the best one from 5 codes (including original) for different > operand sizes. > > It is always interesting to compare different free/non-free software's > speed. > Using the latest versions I get the following times for computing > binomial(2000000,1000000) > > my code: 0.5 sec. > Pari-Gp: 8 sec. > Mathematica: 11 sec. (using gmp, but for this their own code) > Sage: 14 sec. (it is using Pari-Gp) > Gmp/Mpir: 268 sec. "the fastest bignum library on the planet!" > Maple: 1362 sec. (-> what is it doing?!, using gmp) > > Mathematica is non-free, but it is containing a reference guide, from > that > "Factorial, Binomial and related functions use a divide-and-conquer > algorithm to balance the number of digits in subproducts." > This is what I'm doing. > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "mpir-devel" group. To post to this group, send email to mpir-devel@googlegroups.com To unsubscribe from this group, send email to mpir-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/mpir-devel?hl=en -~----------~----~----~----~------~----~------~--~---
