This is the mail archive of the
java-patches@gcc.gnu.org
mailing list for the Java project.
Re: BigInteger.modInverse() fix
- From: Per Bothner <per at bothner dot com>
- To: Mark Wielaard <mark at klomp dot org>
- Cc: java-patches at gcc dot gnu dot org, raif at fl dot net dot au
- Date: Sun, 15 Dec 2002 11:38:01 -0800
- Subject: Re: BigInteger.modInverse() fix
- References: <1039966534.16025.384.camel@elsschot>
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/