[PATCH] BigInteger(int numBits, [int certainty], Random rnd) re-write

[Per Bothner <per at bothner dot com>]

I've fixed and tested this patch.  It seems to produce reasonable
results.  It is presumably faster, though I haven't tested that.
Mark, could you test the patch for your application?

2001-08-24  Per Bothner  <per@bothner.com>

	* java/math/BigInteger.java (init(int,Random)):  New method.
	Move body of constructor <init>(int,Random)) here.
	Re-write it to avoid constructing unneeded temporaries.
	(<init>(int,int,Random)):  Use new init method to avoid constructing
	extra temporary BigIntegers.
	
Index: java/math/BigInteger.java
===================================================================
RCS file: /cvs/gcc/gcc/libjava/java/math/BigInteger.java,v
retrieving revision 1.14
diff -u -r1.14 BigInteger.java
--- BigInteger.java	2001/08/17 22:21:02	1.14
+++ BigInteger.java	2001/08/25 04:28:17
@@ -144,20 +144,36 @@
 
   public BigInteger(int numBits, Random rnd)
   {
-    this(1, randBytes(numBits, rnd));
+    if (numBits < 0)
+      throw new IllegalArgumentException();
+
+    init(numBits, rnd);
   }
 
-  private static byte[] randBytes(int numBits, Random rnd)
+  private void init(int numBits, Random rnd)
   {
-    if (numBits < 0)
-      throw new IllegalArgumentException();
+    int highbits = numBits & 31;
+    if (highbits > 0)
+      highbits = rnd.nextInt() >>> (32 - highbits);
+    int nwords = numBits / 32;
 
-    int extra = numBits % 8;
-    byte[] b = new byte[numBits / 8 + (extra > 0 ? 1 : 0)];
-    rnd.nextBytes(b);
-    if (extra > 0)
-      b[0] &= ~((~0) << (8 - extra));
-    return b;
+    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)
@@ -170,9 +186,7 @@
 	if (isProbablePrime(certainty))
 	  return;
 
-	BigInteger next = new BigInteger(bitLength, rnd);
-	this.ival = next.ival;
-	this.words = next.words;
+	init(bitLength, rnd);
       }
   }
 

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