BigInteger.modInverse() fix

[Per Bothner]

Raif S. Naffah wrote:
>>>>Not necessarirly.  I don't think canonicaliztion of small
>>>>integers is required for correctness, just (space) effiency...
>>>
>>>...and speed, for some numerical algorithms where modulo 2**32 is
>>>enough.
>>
>>canonicalize "in place" (i.e. ignoring the looking in smallFixNums
>>still converts the 1-word integers to use just the 'ival' field
>>without the 'words' array.  The issue is whether the input
>>BigInteger, after "normalization-in-place" is replace by the
>>equivalent BigInteger in the smallFixNums array.
> 
> if the above is a question, then the answer is yes.  see lines #435, 436 
> (after patch is applied).

You're missing my point.  The method canonicalize does three things:
(1) Figure out the minimum number of words needs, and set ival to that.
(2) If the number of words needed is <= 1,
drop the words array, replacing ival by words[0].
(3) If the valus is in the range [minFixNum, maxFixNum]
return this, otherwise return an equivalent element in smallFixInts.

Doing (1) and (2) may be needed for correctness.
Doing (2) is desirable for speed and space (dropping the words array).
It might affect correctness, but only because some methods (such as
equals) assume their arguments are canonicalized.
Doing (3) is to reduce the number of objects that allocated (since
most integers will be small integers).  It does not effect which
algorithms are chosen.

The difference between:
   rem = rem.canonicalize();
and
   rem.canonicalize();
is whether steps (1-3) are done or whether only steps (1-2) are
done.  Steps (1) and (2) are done either way.  Whether (3) is
done will *not* effect which algorithms are used.

> ...unless as was the case, the code in some places was assuming that 
> because one of the arguments was in canonical form, the other one was 
> too.  this is not guarranteed to be the case.
> 
> in the test cases submitted to mauve, the second argument to the 
> extended Euclide algorithm, ends up to be a small int but not in 
> canonical form, the code assumed that .ival can be used; it ends up 
> using '1' (the number of words representing the value), and everything 
> crumbles from then on.

This has nothing to do with whether step (3) is done, only whether
steps (1-2) are done.  Also doing step (3) is a good idea, since
canonicalize does it anyway, it is silly to throw away the result.
*Except* if some later step modifies the returned BigInteger in
place, which of course is not allowed for a BigInteger that may be
referenced by non-private methods, including those in the
smallFixNums array,

For example in divide(BigInteger val), doing this would be
a Bid Idea:
    BigInteger quot = new BigInteger();
    quot = quot.canonicalize();
    divide(this, val, quot, null, TRUNCATE);
In this case you do not want to do step 3 of a canonicalize(),
since then the devide would overwrite ZERO!

I don't know how euclidInv works enough to tell whether
it would be correct to do:
   rem = rem.canonicalize();
instead of:
   rem.canonicalize();
It depends on whether rem is used purely as an input argument or
it is used as an output argument.
-- 
	--Per Bothner
per@bothner.com   http://www.bothner.com/per/