Re: Another BigInteger bug.

[Per Bothner <per at bothner dot com>]

"Boehm, Hans" <hans_boehm@hp.com> writes:

> It looks to me like this patch basically does two things:
> 
> 1) It fixes a problem with the shift count in
> 
> -    words[--nwords] = rnd.nextInt() >>> (numBits % 32);
> 
> This looks clearly wrong to me.  It should be more like (32 - numBits % 32),
> except that numBits == 0 needs to be handled corectly, i.e. the whole word
> needs to be set to 0 in that case.
> 
> 2) It changes the implementation to be based on Random.nextBytes() instead
> of Random.nextInt().
> 
> I think (1) is a huge improvement in correctness but, if I understand the
> code correclty, (2) is probably a mild regression in performance.  I'd
> prefer a patch that only did (1), but this is clearly a net improvement.

(Sorry for not responding earlier.)

Sometimes when people come across a bug instead of trying to
understand the failure, they throw out the existing implementation and
write a new one.  This is not a good practice, especially when the new
implementation may fix the bug, but is otherwise inferior, perhaps
performance-wise.  If a re-write is in order, that needs more
justification than just fixing a bug, unless the bug is fundamental
to the old code.  In this case, I don't believe it is.

Please try replacing the original:
  words[--nwords] = rnd.nextInt() >>> (numBits % 32);
by:
  words[--nwords] = numBits == 0 ? 0 : rnd.next(numBits % 32);

However, I can't say I'm too fond of the old code either.  It
allocates a temporary BigInteger in a BigInteger constructor, which
is wasteful.  (It is especially bad inside a loop in BigInteger(int
bitLength, int certainty, Random rnd).)

So I wrote the following.  Any comments on it?  It is totally
untested; I haven't even even tried compiling it yet.

  public BigInteger(int numBits, Random rnd)
  {
    if (numBits < 0)
      throw new IllegalArgumentException();

    init(numBits, rnd);
  }

  private init(int numBits, Random rnd)
  {
    int highbits = numBits & 31;
    highbits = highbits == 0 ? 0 : rnd.next(highbits);
    int nwords = numBits / 32;

    while (highbits == 0 && nwords > 0)
      {
	highbits = rnd.nextInt();
	--nwords;
      }
    if (nwords == 0 && highbits >= 0)
      {
	ival = highbits;
      }
    else
      {
	ival = highbits < 0 ? nwords + 2 : nwords + 1;
	words = new int[ival];
	words[nwords] = highbits;
	while (--nwords >= 0)
	  words[nwords] = rnd.nextInt();
      }
  }

  public BigInteger(int bitLength, int certainty, Random rnd)
  {
    this(bitLength, rnd);

    // Keep going until we find a probable prime.
    while (true)
      {
	if (isProbablePrime(certainty))
	  return;

	init(bitLength, rnd);
      }
  }

-- 
	--Per Bothner
per@bothner.com   http://www.bothner.com/per/