This is the mail archive of the java-patches@gcc.gnu.org mailing list for the Java project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: BigInteger.modInverse() fix


Mark Wielaard wrote:
+        // quot and rem may not be in canonical form. ensure
+        rem.canonicalize();
+        quot.canonicalize();
Would it make sense to do:

          rem = rem.canonicalize();
          quot = quot.canonicalize();

It probably doesn't matter.

Instead of allocating a BigInteger at each level of
recursion, maybe you could modify euclidInv to:

 private static final void
 euclidInv(BigInteger a, BigInteger b, BigInteger prevDiv,
           BigInteger xy0, BigInteger xy1, BigInteger xy2)

and change the initial call instead of:

        BigInteger rem = new BigInteger();
        BigInteger quot = new BigInteger();
        divide(x, y, quot, rem, FLOOR);
        result = euclidInv(y, rem, quot)[swapped ? 0 : 1];

to:

        BigInteger rem = new BigInteger();
        BigInteger quot = new BigInteger();
        divide(x, y, quot, rem, FLOOR);
        BigInteger xy0 = new BigInteger();
        BigInteger xy1 = new BigInteger();
        BigInteger xy2 = new BigInteger();
        euclidInv(y, rem, quot, xy0, xy1, xy2);
        result = (swapped ? xy0, xy1).canonicalize();

Then each recursive step can re-use xy0, xy1, xy2,
without having to allocate them or the 3-element arrays.
(If you do it this way, you could perhaps skip xy2 say
and pass that as the result.  Sombody who actually
understand the code can probably figure it out.)
--
	--Per Bothner
per@bothner.com   http://www.bothner.com/per/


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]