On Wed, Sep 05, 2012 at 09:25:08AM -0700, Phil Steitz wrote: > On 9/5/12 7:46 AM, [email protected] wrote: > > Author: erans > > Date: Wed Sep 5 14:46:59 2012 > > New Revision: 1381206 > > > > URL: http://svn.apache.org/viewvc?rev=1381206&view=rev > > Log: > > MATH-841 > > Performance improvement in method "gcd(int, int)" (~2 to 4 times faster than > > the previous implementation). Thanks to Sebastien Riou. > > > > Modified: > > > > commons/proper/math/trunk/src/main/java/org/apache/commons/math3/util/ArithmeticUtils.java > > > > Modified: > > commons/proper/math/trunk/src/main/java/org/apache/commons/math3/util/ArithmeticUtils.java > > URL: > > http://svn.apache.org/viewvc/commons/proper/math/trunk/src/main/java/org/apache/commons/math3/util/ArithmeticUtils.java?rev=1381206&r1=1381205&r2=1381206&view=diff > > ============================================================================== > > --- > > commons/proper/math/trunk/src/main/java/org/apache/commons/math3/util/ArithmeticUtils.java > > (original) > > +++ > > commons/proper/math/trunk/src/main/java/org/apache/commons/math3/util/ArithmeticUtils.java > > Wed Sep 5 14:46:59 2012 > > @@ -358,25 +358,25 @@ public final class ArithmeticUtils { > > } > > > > /** > > - * <p> > > - * Gets the greatest common divisor of the absolute value of two > > numbers, > > - * using the "binary gcd" method which avoids division and modulo > > - * operations. See Knuth 4.5.2 algorithm B. This algorithm is due to > > Josef > > - * Stein (1961). > > - * </p> > > + * Computes the greatest common divisor of the absolute value of two > > + * numbers, using the "binary gcd" method which avoids division and > > + * modulo operations. > > The mod operator is used below. Javadoc should be modified to > reflect the implementation. The algorithm appears to be a modified > version of what is in the reference. Modifications should be > called out if possible. I haven't fully understood the > modifications, but it looks like there is some preprocessing of > arguments that speeds up the algorithm. It would be great to > describe how it works or provide an external reference. If we can't > do that, we should just say it is a "modified version" of binary gcd > and drop the statement about not using mod.
Javadoc modified as requested. > I was going to suggest > the that unmodified binary gcd in the private method below for > positive arguments be exposed for usage when both arguments are > known positive, but IIUC what is going on, even in that case it will > be faster to call the exposed method. Do I have that right? I don't know. As it is now, it's not worth exposing a "dangerous" method (until a use-case demonstrates a noticeable performance gain in an actual application). Gilles > [...] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
