[Bug classpath/23189] Remove recursion from java.math.BigInteger.euclidInv()

[b_gs at hotmail dot com]

------- Additional Comments From b_gs at hotmail dot com  2005-08-15 13:19 
-------
This behavior is no longer a problem for me.  There was a bug in the CLRProfiler
tool I was running with that caused the crash on this (
http://www.dotnet247.com/247reference/msgs/52/262050.aspx ).

I did however find an iterative algorithm that will produces much less garbage
if you wish to use it ( http://mathforum.org/library/drmath/view/51895.html ). 
I coded it up but didn't debug it so it may not work right.

-----

    // compute n such that a*n mod b = 1
    private static BigInteger euclidInv(BigInteger a, BigInteger b) {

        // see http://mathforum.org/library/drmath/view/51895.html

        // make positive via mod
        a = a.isNegative() ? a.mod(b) : a;
                
        BigInteger x0 = ONE;
        BigInteger y0 = ZERO;
        BigInteger x1 = ZERO;
        BigInteger y1 = ONE;
        
        BigInteger r0 = a;
        BigInteger r1 = b;
        
        // we reuse these objects on each loop iteration
        // to save the object creation
        BigInteger r = new BigInteger();
        BigInteger q = new BigInteger();
        
        while (!r1.isOne()) {
            if (r1.isZero()) {
                throw new ArithmeticException("not invertible");
            }
                
            divide(r0, r1, q, r, FLOOR);
        
            BigInteger x = add(x0, times(q, x1), -1);
            BigInteger y = add(y0, times(q, y1), -1);
        
            // crank
            r0 = r1;
            r1 = r;
            x0 = x1;
            x1 = x;
            y0 = y1;
            y1 = y;
        }
        
        // result is x1
        if (x1.isNegative()) {
            x1.add(b);
        }
        return x1;      
    }


-----


  public BigInteger modInverse(BigInteger y)
  {
    if (y.isNegative() || y.isZero())
      throw new ArithmeticException("non-positive modulo");

    // Degenerate cases.
    if (y.isOne())
      return ZERO;
    if (isOne())
      return ONE;

    // Use Euclid's algorithm as in gcd() but do this recursively
    // rather than in a loop so we can use the intermediate results as we
    // unwind from the recursion.
    // Used http://www.math.nmsu.edu/~crypto/EuclideanAlgo.html as reference.
    BigInteger result = new BigInteger();
    boolean swapped = false;

    if (y.words == null)
      {
        // The result is guaranteed to be less than the modulus, y (which is
        // an int), so simplify this by working with the int result of this
        // modulo y.  Also, if this is negative, make it positive via modulo
        // math.  Note that BigInteger.mod() must be used even if this is
        // already an int as the % operator would provide a negative result if
        // this is negative, BigInteger.mod() never returns negative values.
        int xval = (words != null || isNegative()) ? mod(y).ival : ival;
        int yval = y.ival;

        // Swap values so x > y.
        if (yval > xval)
          {
            int tmp = xval; xval = yval; yval = tmp;
            swapped = true;
          }
        // Normally, the result is in the 2nd element of the array, but
        // if originally x < y, then x and y were swapped and the result
        // is in the 1st element of the array.
        result.ival =
          euclidInv(yval, xval % yval, xval / yval)[swapped ? 0 : 1];

        // Result can't be negative, so make it positive by adding the
        // original modulus, y.ival (not the possibly "swapped" yval).
        if (result.ival < 0)
          result.ival += y.ival;
      }
    else
      {
        result = euclidInv(this, y);
      }
    
    return result;
  }

-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=23189