There is a graph of expected performance on page 16 of Moller's paper: http://www.lysator.liu.se/~nisse/archive/S0025-5718-07-02017-0.pdf
It looks like the ngcd algorithm is supposed to be the fastest. But it is still clear from the graph that at 1 million bits ngcd is dramatically faster than the accelerated gcd, like 10 times faster. Something is wrong somewhere. Perhaps the version of the patches on Moller's site is broken. But presumably this is the code he used to construct the timings for his paper. Bill. 2008/12/21 Bill Hart <goodwillh...@googlemail.com>: > I see why it is faster. There is a #define in the accelerated gcd > algorithm switching out some of the old code. Now a function called > mpn_ngcd_lehmer is called. > > This is one of Moller's functions, presumably implementing his "new > half gcd algorithm". According to his paper this is supposed to be > faster than the half gcd algorithm of Schoenhage. > > Now I have no idea what is going on. > > Bill. > > 2008/12/21 Bill Hart <goodwillh...@googlemail.com>: >> The function mpz_gcd is defined in the file /mpz/gcd. In the latest >> revision of MPIR it invokes a macro GCD_BODY(mpn_gcd). This macro is >> just a generic wrapper for an mpn_gcd like function. It can be invoked >> with any function which observes the syntax of mpn_gcd as a parameter. >> But currently mpz_gcd is invoked with parameter mpn_gcd. >> >> mpn_gcd is defined in the file /mpn/generic/gcd.c. Currently it >> implements the algorithm known as the accelerated gcd algorithm: >> >> K. Weber, The accelerated integer GCD algorithm, ACM Transactions on >> Mathematical Software, v. 21 (March), 1995, pp. 111-122. >> >> as implemented by Ken Weber in 2002. It does *NOT* use Moller's >> patches or a half gcd algorithm. >> >> Instead, mpn_gcd should be modified to actually call mpn_hgcd. >> >> As you say, it may be possible to have some kind of tuned wrapper >> which chooses the best algorithm depending on the input. >> >> I don't know why mpz_gcd is currently faster than it used to be. >> Perhaps some other difference in our code base accounts for that. >> >> The whole point is, Moller's algorithm is a half gcd algorithm. This >> is asymptotically faster than the accelerated gcd algorithm (it is >> subquadratic). This means that as the sizes increase the distance >> between the before and after timings should become more and more >> dramatic. >> >> One person that might be able to help is Moller. He seemed nice enough >> when I spoke to him via email. I don't know what the intended usage of >> his functions is, and I haven't checked to see how well documented >> they are. Presumably one wouldn't call hgcd when one of the inputs is >> very small and the other very large. There also appear to be numerous >> other functions in his files and I haven't looked at his documentation >> or paper to see what situations they are supposed to be advantageous >> in. >> >> I kind of assumed that you were sorting all this out. >> >> Bill. >> >> 2008/12/21 Jason Martin <jason.worth.mar...@gmail.com>: >>> >>> What about the figures? I see that the new mpn_gcd is faster than the >>> GMP v. 4.2 mpn_gcd. >>> >>> I'm confused about what you want me to do. I thought the assignment >>> was to put Moller's v2.1 patches into MPIR. I did that. The patches >>> are there and they DO show a difference with a high enough limb count. >>> >>> I can't use the Moller patches on the GMP webpage because they are GPL v. 3. >>> >>> Jason Worth Martin >>> Asst. Professor of Mathematics >>> http://www.math.jmu.edu/~martin >>> >>> >>> >>> On Sat, Dec 20, 2008 at 7:12 PM, Bill Hart <goodwillh...@googlemail.com> >>> wrote: >>>> >>>> You need to look at the figures on the GMP website and look at the >>>> asymptotics. That has nothing to do with Magma. >>>> >>>> Bill. >>>> >>>> 2008/12/21 Jason Martin <jason.worth.mar...@gmail.com>: >>>>> >>>>>> By the way, the code you posted has a variable missing in the final >>>>>> printf. It always returns 0.00. >>>>> >>>>> Sorry, that was a version control issue. The numbers I posted below >>>>> are for correct code (with the "result" variable printed. >>>>> >>>>> I don't get the error message that you are reporting when building. >>>>> I'll try building on sage.math and see what happens. >>>>> >>>>> I'm also confused about what exactly you're saying the problem is. My >>>>> testing shows that for big enough numbers, the Moller patches in MPIR >>>>> are faster than the un-patched MPIR. I'm not comparing it against >>>>> Magma because I don't have any basis for the comparison. >>>>> >>>>> Perhaps you should send me the exact numbers you're talking about and >>>>> I'll try them with: >>>>> >>>>> MPIR rev 1487 (pre-patch) >>>>> MPIR current >>>>> and >>>>> GMP 4.2.4 >>>>> >>>>> --jason >>>>> >>>>> > >>>>> >>>> >>>> > >>>> >>> >>> >>> >>> >> > --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
