(original) (raw)

/* * Copyright (c) 1998, 2013, Oracle and/or its affiliates. All rights reserved. * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * * This code is free software; you can redistribute it and/or modify it * under the terms of the GNU General Public License version 2 only, as * published by the Free Software Foundation. * * This code is distributed in the hope that it will be useful, but WITHOUT * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License * version 2 for more details (a copy is included in the LICENSE file that * accompanied this code). * * You should have received a copy of the GNU General Public License version * 2 along with this work; if not, write to the Free Software Foundation, * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. * * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA * or visit www.oracle.com if you need additional information or have any * questions. */ /* * @test * @bug 4181191 4161971 4227146 4194389 4823171 4624738 4812225 4837946 * @summary tests methods in BigInteger * @run main/timeout=400 BigIntegerTest * @author madbot */ import java.io.File; import java.io.FileInputStream; import java.io.FileOutputStream; import java.io.ObjectInputStream; import java.io.ObjectOutputStream; import java.math.BigInteger; import java.util.Random; import java.lang.reflect.Array; import java.lang.reflect.Constructor; import java.lang.reflect.Field; import java.lang.reflect.Method; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.List; /** * This is a simple test class created to ensure that the results * generated by BigInteger adhere to certain identities. Passing * this test is a strong assurance that the BigInteger operations * are working correctly. * * Five arguments may be specified which give the number of * decimal digits you desire in the five batches of test numbers. * * The tests are performed on arrays of random numbers which are * generated by a Random class as well as special cases which * throw in boundary numbers such as 0, 1, maximum sized, etc. * */ public class BigIntegerTest { // // Bit large number thresholds based on the int thresholds // defined in BigInteger itself: // // KARATSUBA_THRESHOLD = 50 ints = 1600 bits // TOOM_COOK_THRESHOLD = 75 ints = 2400 bits // KARATSUBA_SQUARE_THRESHOLD = 90 ints = 2880 bits // TOOM_COOK_SQUARE_THRESHOLD = 140 ints = 4480 bits // // SCHOENHAGE_BASE_CONVERSION_THRESHOLD = 8 ints = 256 bits // // BURNIKEL_ZIEGLER_THRESHOLD = 50 ints = 1600 bits // static final int BITS_KARATSUBA = 1600; static final int BITS_TOOM_COOK = 2400; static final int BITS_KARATSUBA_SQUARE = 2880; static final int BITS_TOOM_COOK_SQUARE = 4480; static final int BITS_SCHOENHAGE_BASE = 256; static final int BITS_BURNIKEL_ZIEGLER = 1600; static final int ORDER_SMALL = 60; static final int ORDER_MEDIUM = 100; // #bits for testing Karatsuba and Burnikel-Ziegler static final int ORDER_KARATSUBA = 1800; // #bits for testing Toom-Cook static final int ORDER_TOOM_COOK = 3000; // #bits for testing Schoenhage-Strassen and Barrett static final int ORDER_SS_BARRETT = 4000000; // #bits for testing Karatsuba squaring static final int ORDER_KARATSUBA_SQUARE = 3200; // #bits for testing Toom-Cook squaring static final int ORDER_TOOM_COOK_SQUARE = 4600; static final int SIZE = 1000; // numbers per batch static final int REDUCED_SIZE = 10; // numbers per batch in the Schoenhage-Strassen/Barrett range static Random rnd = new Random(); static boolean failure = false; public static void pow(int order) { int failCount1 = 0; for (int i=0; i<size; 0="" i++)="" {="" test="" identity="" x^power="=" x*x*x="" ...="" *x="" int="" power="rnd.nextInt(6)" +="" 2;="" biginteger="" x="fetchNumber(order);" y="x.pow(power);" z="x;" for="" (int="" j="1;" j<power;="" j++)="" if="" (!y.equals(z))="" failcount1++;="" }="" report("pow="" "="" order="" bits",="" failcount1);="" public="" static="" void="" square(int="" order)="" failcount1="0;" iterations="order<ORDER_SS_BARRETT" ?="" size="" :="" reduced_size;="" i="0;" i<iterations;="" x^2="=" x*x="" xx="x.multiply(x);" x2="x.pow(2);" (!x2.equals(xx))="" report("square="" arithmetic(int="" failcount="0;" while(x.compareto(biginteger.zero)="" !="1)" while(x.compareto(y)="=" -1)="" (y.equals(biginteger.zero))="" ((x="" y))*y="" x%y="" -="" using="" separate="" divide()="" and="" remainder()="" baz="x.divide(y);" (!baz.equals(biginteger.zero))="" failcount++;="" report("arithmetic="" failcount);="" i<100;="" divideandremainder()="" baz[]="x.divideAndRemainder(y);" baz[0]="baz[0].multiply(y);" (!baz[0].equals(biginteger.zero))="" ii="" **="" *="" sanity="" karatsuba="" 3-way="" toom-cook="" multiplication.="" each="" of="" the="" multiplication="" thresholds,="" construct="" two="" factors="" with="" a="" mag="" array="" one="" element="" shorter="" than="" threshold,="" most="" significant="" bit="" set="" rest="" bits="" random.="" these="" numbers="" will="" therefore="" be="" below="" threshold="" but="" shifted="" left="" above="" threshold.="" call="" 'u'="" 'v'="" define="" random="" shifts="" 'a'="" 'b'="" in="" range="" [1,32].="" then="" we="" have="" <pre=""> * (u << a)*(v << b) = (u*v) << (a + b) * * For Karatsuba multiplication, the right hand expression will be evaluated * using the standard naive algorithm, and the left hand expression using * the Karatsuba algorithm. For 3-way Toom-Cook multiplication, the right * hand expression will be evaluated using Karatsuba multiplication, and the * left hand expression using 3-way Toom-Cook multiplication. */ public static void multiplyLarge() { int failCount = 0; BigInteger base = BigInteger.ONE.shiftLeft(BITS_KARATSUBA - 32 - 1); for (int i=0; i<size; 32="" i++)="" {="" biginteger="" x="fetchNumber(BITS_KARATSUBA" -="" 1);="" u="base.add(x);" int="" a="1" +="" rnd.nextint(31);="" w="u.shiftLeft(a);" y="fetchNumber(BITS_KARATSUBA" v="base.add(y);" b="1" rnd.nextint(32);="" z="v.shiftLeft(b);" multiplyresult="u.multiply(v).shiftLeft(a" b);="" karatsubamultiplyresult="w.multiply(z);" if="" (!multiplyresult.equals(karatsubamultiplyresult))="" failcount++;="" }="" report("multiplylarge="" karatsuba",="" failcount);="" failcount="0;" base="base.shiftLeft(BITS_TOOM_COOK" bits_karatsuba);="" for="" (int="" i="0;" i<size;="" u2="u.shiftLeft(1);" v2="v.shiftLeft(1);" toomcookmultiplyresult="u2.multiply(v2);" (!multiplyresult.equals(toomcookmultiplyresult))="" toom-cook",="" **="" *="" sanity="" test="" karatsuba="" and="" 3-way="" toom-cook="" squaring.="" this="" is="" analogous="" to="" {@link="" abstractmethoderror#multiplylarge}="" with="" both="" factors="" being="" equal.="" the="" squaring="" methods="" will="" not="" be="" tested="" unless="" <code="">bigInteger.multiply(bigInteger) tests whether * the parameter is the same instance on which the method is being invoked * and calls square() accordingly. */ public static void squareLarge() { int failCount = 0; BigInteger base = BigInteger.ONE.shiftLeft(BITS_KARATSUBA_SQUARE - 32 - 1); for (int i=0; i<size; 32="" i++)="" {="" biginteger="" x="fetchNumber(BITS_KARATSUBA_SQUARE" -="" 1);="" u="base.add(x);" int="" a="1" +="" rnd.nextint(31);="" w="u.shiftLeft(a);" squareresult="u.multiply(u).shiftLeft(2*a);" karatsubasquareresult="w.multiply(w);" if="" (!squareresult.equals(karatsubasquareresult))="" failcount++;="" }="" report("squarelarge="" karatsuba",="" failcount);="" failcount="0;" base="base.shiftLeft(BITS_TOOM_COOK_SQUARE" bits_karatsuba_square);="" for="" (int="" i="0;" i<size;="" toomcooksquareresult="w.multiply(w);" (!squareresult.equals(toomcooksquareresult))="" toom-cook",="" **="" *="" sanity="" test="" burnikel-ziegler="" division.="" the="" division="" algorithm="" is="" used="" when="" each="" of="" dividend="" and="" divisor="" has="" at="" least="" specified="" number="" ints="" in="" its="" representation.="" this="" based="" on="" observation="" that="" {@code="" z="v*pow(2,b)}" where="" abs(u)=""> abs(v)} and {@code a > b && b > 0}, then if * {@code w/z = q1*z + r1} and {@code u/v = q2*v + r2}, then * {@code q1 = q2*pow(2,a-b)} and {@code r1 = r2*pow(2,b)}. The test * ensures that {@code v} is just under the B-Z threshold and that {@code w} * and {@code z} are both over the threshold. This implies that {@code u/v} * uses the standard division algorithm and {@code w/z} uses the B-Z * algorithm. The results of the two algorithms are then compared using the * observation described in the foregoing and if they are not equal a * failure is logged. */ public static void divideLarge() { int failCount = 0; BigInteger base = BigInteger.ONE.shiftLeft(BITS_BURNIKEL_ZIEGLER - 33); for (int i=0; i<size; i++)="" {="" biginteger="" addend="new" biginteger(bits_burnikel_ziegler="" -="" 34,="" rnd);="" v="base.add(addend);" u="v.multiply(BigInteger.valueOf(2" +="" rnd.nextint(short.max_value="" 1)));="" if(rnd.nextboolean())="" }="" int="" a="17" rnd.nextint(16);="" b="1" w="u.multiply(BigInteger.valueOf(1L" <<="" a));="" z="v.multiply(BigInteger.valueOf(1L" b));="" biginteger[]="" divideresult="u.divideAndRemainder(v);" divideresult[0]="divideResult[0].multiply(BigInteger.valueOf(1L" (a="" b)));="" divideresult[1]="divideResult[1].multiply(BigInteger.valueOf(1L" bzresult="w.divideAndRemainder(z);" if="" (divideresult[0].compareto(bzresult[0])="" !="0" ||="" divideresult[1].compareto(bzresult[1])="" failcount++;="" report("dividelarge",="" failcount);="" public="" static="" void="" schoenhagestrassen(int="" order)="" throws="" exception="" failcount="0;" test="" edge="" cases="" by="" multiplying="" numbers="" of="" the="" form="" 2^n="" {-1,0,1}="" for="" (int="" i="0;" i<10;="" m="1" (23+rnd.nextint(3));="" x="ONE.shiftLeft(m);" xd="BigInteger.valueOf(rnd.nextInt(3)" 1);="" n="1" y="ONE.shiftLeft(n);" yd="BigInteger.valueOf(rnd.nextInt(3)" product="x.add(xd).multiply(y.add(yd));" expected="ONE.shiftLeft(m" n);="" add="" x.multiply(yd)="" y.multiply(xd)="" (!product.equals(expected))="" squaring="" method="" squaremethod="BigInteger.class.getDeclaredMethod("square");" squaremethod.setaccessible(true);="" square="(BigInteger)squareMethod.invoke(x.add(xd));" *="" m);="" 2*x.multiply(xd)="" (!square.equals(expected))="" multithreaded="" multiplyschoenhagestrassen()="" multiplyschoenhagestrassenmethod="BigInteger.class.getDeclaredMethod("multiplySchoenhageStrassen"," biginteger.class,="" int.class);="" multiplyschoenhagestrassenmethod.setaccessible(true);="" biginteger(order_ss_barrett,="" c1="a.multiply(b," 2+rnd.nextint(10));="" c2="a.multiply(b);" (!c1.equals(c2))="" verify="" that="" idft(dft(a))="a" class<?=""> mutableModFnClass = Class.forName("java.math.MutableModFn"); Constructor mutableModFnCtor = mutableModFnClass.getDeclaredConstructor(long[].class); mutableModFnCtor.setAccessible(true); Field digitsField = mutableModFnClass.getDeclaredField("digits"); digitsField.setAccessible(true); Method dftMethod = BigInteger.class.getDeclaredMethod("dft", Array.newInstance(mutableModFnClass, 0).getClass(), int.class, int.class); dftMethod.setAccessible(true); Method idftMethod = BigInteger.class.getDeclaredMethod("idft", Array.newInstance(mutableModFnClass, 0).getClass(), int.class, int.class); idftMethod.setAccessible(true); for (int k=0; k<100; k++) { int m = 10 + rnd.nextInt(8); int n = m/2 + 1; long[][] a = createRandomDftArray(m, n); long[][] aOrig = new long[a.length][]; for (int i=0; i<a.length; 4="" i++)="" aorig[i]="a[i].clone();" int="" omega="m%2==0" ?="" :="" 2;="" object="" vector="Array.newInstance(mutableModFnClass," a.length);="" for="" (int="" i="0;" i<a.length;="" array.set(vector,="" i,="" mutablemodfnctor.newinstance(a[i]));="" dftmethod.invoke(null,="" vector,="" omega,="" 1);="" idftmethod.invoke(null,="" i<aorig.length;="" {="" long[]="" origdigits="(long[])digitsField.get(Array.get(vector," i));="" if="" (!arrays.equals(origdigits,="" aorig[i]))="" failcount++;="" }="" test="" mutablemodfn.multiply()="" method="" multiplymethod="mutableModFnClass.getDeclaredMethod("multiply"," mutablemodfnclass);="" multiplymethod.setaccessible(true);="" reducemethod="mutableModFnClass.getDeclaredMethod("reduce");" reducemethod.setaccessible(true);="" constructor<biginteger=""> bigintCtor = BigInteger.class.getDeclaredConstructor(int.class, int[].class); bigintCtor.setAccessible(true); for (int i=0; i<100; i++) { int n = 6 + rnd.nextInt(10); long[] a = createRandomModFn(n); long[] b = createRandomModFn(n); int[] aInt = toIntArray(a); BigInteger aBigInt = bigintCtor.newInstance(1, aInt); int[] bInt = toIntArray(b); BigInteger bBigInt = bigintCtor.newInstance(1, bInt); BigInteger expected = aBigInt.multiply(bBigInt).mod(fermat(n)); Object aMutable = mutableModFnCtor.newInstance(a); Object bMutable = mutableModFnCtor.newInstance(b); multiplyMethod.invoke(aMutable, bMutable); long[] c = (long[])digitsField.get(aMutable); int[] cInt = toIntArray(c); BigInteger actual = bigintCtor.newInstance(1, cInt); if (!actual.equals(expected)) failCount++; } // test MutableModFn.square() Method squareModFnMethod = mutableModFnClass.getDeclaredMethod("square"); squareModFnMethod.setAccessible(true); for (int i=0; i<100; i++) { int n = 6 + rnd.nextInt(10); long[] a = createRandomModFn(n); int[] aInt = toIntArray(a); BigInteger aBigInt = bigintCtor.newInstance(1, aInt); BigInteger expected = aBigInt.multiply(aBigInt).mod(fermat(n)); Object aMutable = mutableModFnCtor.newInstance(a); squareModFnMethod.invoke(aMutable); long[] c = (long[])digitsField.get(aMutable); int[] cInt = toIntArray(c); BigInteger actual = bigintCtor.newInstance(1, cInt); if (!actual.equals(expected)) failCount++; } // test MutableModFn.add() Method addMethod = mutableModFnClass.getDeclaredMethod("add", mutableModFnClass); addMethod.setAccessible(true); Method toIntArrayOddMethod = mutableModFnClass.getDeclaredMethod("toIntArrayOdd", long[].class); toIntArrayOddMethod.setAccessible(true); for (int k = 0; k<100; k++) { int n = 6 + rnd.nextInt(10); long[] aArr = createRandomModFn(n); long[] bArr = createRandomModFn(n); int[] aArrInt = toIntArray(aArr); BigInteger a = bigintCtor.newInstance(1, aArrInt); int[] bArrInt = toIntArray(bArr); BigInteger b = bigintCtor.newInstance(1, bArrInt); BigInteger expected = a.add(b).mod(fermat(n)); Object aMutable = mutableModFnCtor.newInstance(aArr); Object bMutable = mutableModFnCtor.newInstance(bArr); addMethod.invoke(aMutable, bMutable); aArr = (long[])digitsField.get(aMutable); aArrInt = toIntArray(aArr); BigInteger actual = bigintCtor.newInstance(1, aArrInt); if (!actual.equals(expected)) failCount++; } // test MutableModFn.subtract() Method subtractMethod = mutableModFnClass.getDeclaredMethod("subtract", mutableModFnClass); subtractMethod.setAccessible(true); for (int k = 0; k<100; k++) { int n = 6 + rnd.nextInt(10); long[] aArr = createRandomModFn(n); long[] bArr = createRandomModFn(n); int[] aArrInt = toIntArray(aArr); BigInteger a = bigintCtor.newInstance(1, aArrInt); int[] bArrInt = toIntArray(bArr); BigInteger b = bigintCtor.newInstance(1, bArrInt); BigInteger expected = a.subtract(b).mod(fermat(n)); Object aMutable = mutableModFnCtor.newInstance(aArr); Object bMutable = mutableModFnCtor.newInstance(bArr); subtractMethod.invoke(aMutable, bMutable); aArr = (long[])digitsField.get(aMutable); aArrInt = toIntArray(aArr); BigInteger actual = bigintCtor.newInstance(1, aArrInt); if (!actual.equals(expected)) failCount++; } // test MutableModFn.shiftLeft() against BigInteger.shiftLeft().mod(Fn) Method shiftLeftMethod = mutableModFnClass.getDeclaredMethod("shiftLeft", int.class, mutableModFnClass); shiftLeftMethod.setAccessible(true); for (int k = 0; k<100; k++) { int n = 6 + rnd.nextInt(10); long[] aArr = createRandomModFn(n); long[] bArr = new long[aArr.length]; int shiftDistance = rnd.nextInt(1 << (n+1)); int[] aArrInt = toIntArray(aArr); BigInteger a = bigintCtor.newInstance(1, aArrInt); BigInteger expected = a.shiftLeft(shiftDistance).mod(fermat(n)); Object aMutable = mutableModFnCtor.newInstance(aArr); Object bMutable = mutableModFnCtor.newInstance(bArr); shiftLeftMethod.invoke(aMutable, shiftDistance, bMutable); bArr = (long[])digitsField.get(bMutable); int[] bArrInt = toIntArray(bArr); BigInteger actual = bigintCtor.newInstance(1, bArrInt); if (!actual.equals(expected)) failCount++; } // test MutableModFn.shiftRight() against BigInteger.multiply(2^(-shiftDistance)).mod(Fn) Method shiftRightMethod = mutableModFnClass.getDeclaredMethod("shiftRight", int.class, mutableModFnClass); shiftRightMethod.setAccessible(true); for (int k = 0; k<100; k++) { int n = 6 + rnd.nextInt(10); long[] aArr = createRandomModFn(n); long[] bArr = new long[aArr.length]; int shiftDistance = rnd.nextInt(1 << (n+1)); BigInteger Fn = fermat(n); BigInteger inv2 = Fn.add(ONE).divide(TWO); // 2^(-1) mod Fn BigInteger inv = inv2.modPow(BigInteger.valueOf(shiftDistance), Fn); // 2^(-shiftDistance) mod Fn int[] aArrInt = toIntArray(aArr); BigInteger a = bigintCtor.newInstance(1, aArrInt); BigInteger expected = a.multiply(inv).mod(Fn); Object aMutable = mutableModFnCtor.newInstance(aArr); Object bMutable = mutableModFnCtor.newInstance(bArr); shiftRightMethod.invoke(aMutable, shiftDistance, bMutable); bArr = (long[])digitsField.get(bMutable); int[] bArrInt = toIntArray(bArr); BigInteger actual = bigintCtor.newInstance(1, bArrInt); if (!actual.equals(expected)) failCount++; } // test MutableModFn.shiftLeft() and MutableModFn.shiftRight() by doing multiple shifts which should cancel each other out for (int k = 0; k<100; k++) { int n = 6 + rnd.nextInt(10); int bitLen = (1<<n) +="" 1;="" pick="" random="" shift="" amounts="" whose="" sum="" is="" zero="" list<integer=""> amounts = new ArrayList(); int count = 1 + rnd.nextInt(20); int total = 0; for (int i = 0; i < count; i++) { int amount = rnd.nextInt(bitLen); amounts.add(amount); total += amount; } while (total > 0) { int amount = Math.min(rnd.nextInt(bitLen), total); amounts.add(-amount); total -= amount; } Collections.shuffle(amounts); long[] a = createRandomModFn(n); long[] aOrig = a.clone(); Object aMutable = mutableModFnCtor.newInstance(a); for (int amount: amounts) { Object bMutable = mutableModFnCtor.newInstance(new long[a.length]); if (amount > 0) shiftLeftMethod.invoke(aMutable, amount, bMutable); else shiftRightMethod.invoke(aMutable, -amount, bMutable); aMutable = bMutable; } reduceMethod.invoke(aMutable); a = (long[])digitsField.get(aMutable); if (!Arrays.equals(a, aOrig)) failCount++; } // test MutableModFn.reduce() for (int k = 0; k<100; k++) { int n = 6 + rnd.nextInt(15); long[] a = createRandomModFn(n); a[0] = rnd.nextLong(); // test all long values, not just 0 and 1 long[] aOrig = a.clone(); BigInteger Fn = fermat(n); int[] aOrigInt = toIntArray(aOrig); BigInteger expected = bigintCtor.newInstance(1, aOrigInt).mod(Fn); Object aMutable = mutableModFnCtor.newInstance(a); reduceMethod.invoke(aMutable); a = (long[])digitsField.get(aMutable); int[] aInt = toIntArray(a); BigInteger actual = bigintCtor.newInstance(1, aInt); if (!actual.equals(expected)) failCount++; if (actual.compareTo(Fn) >= 0) failCount++; } // test MutableModFn.reduceWide() Method reduceWideMethod = mutableModFnClass.getDeclaredMethod("reduceWide", long[].class); reduceWideMethod.setAccessible(true); for (int k = 0; k<100; k++) { int n = 6 + rnd.nextInt(15); int len = 1 << (n + 1 - 6); long[] a = createRandomArrayLong(len); long[] aOrig = a.clone(); BigInteger Fn = fermat(n); int[] aOrigInt = toIntArray(aOrig); BigInteger expected = bigintCtor.newInstance(1, aOrigInt).mod(Fn); reduceWideMethod.invoke(null, a); int[] aInt = (int[])toIntArrayOddMethod.invoke(null, a); BigInteger actual = bigintCtor.newInstance(1, aInt); if (!actual.equals(expected)) failCount++; if (actual.compareTo(Fn) >= 0) failCount++; } // test MutableModFn.toIntArray() and MutableModFn.toLongArray() Method toLongArrayEvenMethod = mutableModFnClass.getDeclaredMethod("toLongArrayEven", int[].class); toLongArrayEvenMethod.setAccessible(true); for (int i=0; i<1000; i++) { int n = 2 + rnd.nextInt(1000); int[] a = createRandomArray(n); long[] b = n%2==0 ? (long[])toLongArrayEvenMethod.invoke(null, a) : toLongArrayOdd(a); int[] c = n%2==0 ? toIntArray(b) : (int[])toIntArrayOddMethod.invoke(null, b); if (!Arrays.equals(a, c)) failCount++; } // test addModPow2 Method addModPow2Method = BigInteger.class.getDeclaredMethod("addModPow2", int[].class, int[].class, int.class); addModPow2Method.setAccessible(true); for (int k = 0; k<100; k++) { int n = 6 + rnd.nextInt(15); int len = 1 << (n + 1 - 5); int[] aArr = createRandomArray(len); aArr[0] &= 0x7FFFFFFF; // make sure the most significant int doesn't overflow BigInteger a = bigintCtor.newInstance(1, aArr); int[] bArr = createRandomArray(len); bArr[0] &= 0x7FFFFFFF; // make sure the most significant int doesn't overflow BigInteger b = bigintCtor.newInstance(1, bArr); int numBits = rnd.nextInt(n); BigInteger pow2 = BigInteger.valueOf(1<<numbits); 1="" biginteger="" expected="a.add(b).mod(pow2);" addmodpow2method.invoke(null,="" aarr,="" barr,="" numbits);="" actual="bigintCtor.newInstance(1," aarr);="" if="" (!actual.equals(expected))="" failcount++;="" }="" test="" submodpow2="" method="" submodpow2method="BigInteger.class.getDeclaredMethod("subModPow2"," int[].class,="" int.class);="" submodpow2method.setaccessible(true);="" for="" (int="" k="0;" k<100;="" k++)="" {="" int="" n="6" +="" rnd.nextint(15);="" len="1" <<="" (n="" -="" 5);="" int[]="" aarr="createRandomArray(len);" aarr[0]="" &="0x7FFFFFFF;" make="" sure="" the="" most="" significant="" doesn't="" overflow="" a="bigintCtor.newInstance(1," barr="createRandomArray(len);" barr[0]="" b="bigintCtor.newInstance(1," barr);="" numbits="rnd.nextInt(n);" pow2="BigInteger.valueOf(1<<numBits);" submodpow2method.invoke(null,="" splitbits="" splitbitsmethod="BigInteger.class.getDeclaredMethod("splitBits"," splitbitsmethod.setaccessible(true);="" rnd.nextint(1000);="" piecesize="1" smallrandom(n-1,="" rnd);="" int[][]="" pieces="(int[][])splitBitsMethod.invoke(null," piecesize);="" i="pieces.length-1;">=0; i--) { int[] piece = pieces[i]; BigInteger pieceBigInt = bigintCtor.newInstance(1, piece); expected = expected.shiftLeft(pieceSize).add(pieceBigInt); } if (!actual.equals(expected)) failCount++; } // test addShifted Method addShiftedMethod = BigInteger.class.getDeclaredMethod("addShifted", int[].class, int[].class, int.class); addShiftedMethod.setAccessible(true); for (int k = 0; k<100; k++) { int[] aArr = createRandomArray(1 + rnd.nextInt(1000)); BigInteger a = bigintCtor.newInstance(1, aArr); int offset = rnd.nextInt(aArr.length); int[] bArr = createRandomArray(1 + rnd.nextInt(1000)); BigInteger b = bigintCtor.newInstance(1, bArr); addShiftedMethod.invoke(null, aArr, bArr, offset); BigInteger actual = bigintCtor.newInstance(1, aArr); BigInteger mask = ONE.shiftLeft(aArr.length*32).subtract(ONE); BigInteger expected = a.add(b.shiftLeft(offset*32)).and(mask); if (!actual.equals(expected)) failCount++; } // test appendBits Method appendBitsMethod = BigInteger.class.getDeclaredMethod("appendBits", int[].class, int.class, int[].class, int.class, int.class); appendBitsMethod.setAccessible(true); for (int k = 0; k<100; k++) { int[] src = createRandomArray(1 + rnd.nextInt(1000)); BigInteger srcBigInt = bigintCtor.newInstance(1, src); int[] dest = new int[src.length]; int valBits = 1 + smallRandom(src.length*32-1, rnd); int padBits = 1 + smallRandom(src.length*32-1, rnd); BigInteger mask = ONE.shiftLeft(valBits).subtract(ONE); int srcIndex = 0; int destBits = 0; BigInteger expected = ZERO; while (srcIndex+(valBits+31)/32 0) dest = Arrays.copyOfRange(dest, dest.length-(destBits+31)/32, dest.length); BigInteger actual = bigintCtor.newInstance(1, dest); if (!actual.equals(expected)) failCount++; } report("Schoenhage-Strassen", failCount); } // like Random.nextInt(int) but favors small numbers private static int smallRandom(int n, Random rnd) { return (int)(n * Math.pow(rnd.nextDouble(), 5)); } private static int[] createRandomArray(int length) { int[] a = new int[length]; for (int i=0; i<a.length; 6="" i++)="" a[i]="rnd.nextInt();" return="" a;="" }="" private="" static="" long[]="" createrandomarraylong(int="" length)="" {="" a="new" long[length];="" for="" (int="" i="0;" i<a.length;="" **="" *="" returns="" random="" number="" modulo="" 2^2^n+1.="" the="" results="" are="" biased="" towards="" special="" case="" 2^2^n.="" @param="" n="" must="" be="" or="" greater="" @return="" an="" array="" of="" length="" ceil((2^n+1)="" 64.0)="" createrandommodfn(int="" n)="" int="" +="" 1;="" if="" (rnd.nextint(5)="=" 0)="" a[0]="1;" 2^2^n="" else="" leave="" zero,="" make="" everything="" long[][]="" createrandomdftarray(int="" m,="" numelements="m%2==0" ?="" 1<<n="" :="" 1<<(n+1);="" =="" 2;="" long[numelements][];="" int[]="" tointarray(long[]="" digits)="" intdigits="new" int[digits.length*2];="" i<digits.length;="" intdigits[2*i]="(int)(digits[i]">>> 32); intDigits[2*i+1] = (int)(digits[i] & -1); } return intDigits; } /** digits.length must be an odd number */ public static long[] toLongArrayOdd(int[] digits) { long[] longDigits = new long[digits.length/2+1]; longDigits[0] = digits[0]; for (int i=1; i<longdigits.length; i++)="" longdigits[i]="(((long)digits[2*i-1])<<32)" |="" (digits[2*i]&0xffffffffl);="" return="" longdigits;="" }="" **="" returns="" the="" n-th="" fermat="" number="" *="" private="" static="" biginteger="" fermat(int="" n)="" throws="" exception="" {="" constructor<biginteger=""> bigintCtor = BigInteger.class.getDeclaredConstructor(int.class, int[].class); bigintCtor.setAccessible(true); int length = (1<<(n-5)) + 1; int[] FnArr = new int[length]; FnArr[0] = 1; FnArr[FnArr.length-1] = 1; return bigintCtor.newInstance(1, FnArr); } private static void inverse() throws Exception { int failCount = 0; Method inverseMethod = BigInteger.class.getDeclaredMethod("inverse", int.class, int.class); inverseMethod.setAccessible(true); for (int i=0; i<reduced_size; i++)="" {="" biginteger="" a;="" do="" a="fetchNumber(ORDER_SS_BARRETT);" }="" while="" (a.compareto(zero)="" <="0);" int="" n="rnd.nextInt(a.bitLength());" expected="BigInteger.ONE.shiftLeft(a.bitLength()+n).divide(a);" actual="(BigInteger)inverseMethod.invoke(a," n,="" 1+rnd.nextint(4));="" if="" (actual.subtract(expected).abs().compareto(one)=""> 1) failCount++; } report("Inverse", failCount); } public static void bitCount() { int failCount = 0; for (int i=0; i<size*10; 0="" 1="" i++)="" {="" int="" x="rnd.nextInt();" biginteger="" bigx="BigInteger.valueOf((long)x);" bit="(x" <="" ?="" :="" 1);="" tmp="x," bitcount="0;" for="" (int="" j="0;" j<32;="" j++)="" +="((tmp" &="" 1)="=" 0);="">>= 1; } if (bigX.bitCount() != bitCount) { //System.err.println(x+": "+bitCount+", "+bigX.bitCount()); failCount++; } } report("Bit Count", failCount); } public static void bitLength() { int failCount = 0; for (int i=0; i<size*10; 0="" i++)="" {="" int="" x="rnd.nextInt();" biginteger="" bigx="BigInteger.valueOf((long)x);" signbit="(x" <="" ?="" 0x80000000="" :="" 0);="" tmp="x," bitlength,="" j;="" for="" (j="0;" j<32="" &&="" (tmp="" &="" 0x80000000)="=signBit;" j++)="" <<="1;" bitlength="32" -="" if="" (bigx.bitlength()="" !="bitLength)" system.err.println(x+":="" "+bitlength+",="" "+bigx.bitlength());="" failcount++;="" }="" report("bitlength",="" failcount);="" public="" static="" void="" bitops(int="" order)="" failcount1="0," failcount2="0," failcount3="0;" (int="" i="0;" i<size*5;="" y;="" test="" setbit="" and="" clearbit="" (and="" testbit)="" (x.signum()="" 0)="" y="BigInteger.valueOf(-1);" j="0;" j<x.bitlength();="" (!x.testbit(j))="" else="" (x.testbit(j))="" (!x.equals(y))="" failcount1++;="" flipbit="" -1="" (x.signum()<0="" ^="" x.testbit(j))="" failcount2++;="" report("clearbit="" testbit="" "="" +="" order="" bits",="" failcount1);="" report("flipbit="" failcount2);="" getlowestsetbit()="" k="x.getLowestSetBit();" (k="" failcount3++;="" z="x.and(x.negate());" j<z.bitlength()="" !z.testbit(j);="" ;="" report("getlowestsetbit="" failcount3);="" bitwise(int="" identity="" x^y="=" x|y="" &~="" x&y="" failcount="0;" i<size;="" w="x.or(y).andNot(x.and(y));" (!z.equals(w))="" report("logic="" (^="" |="" ~)="" ~(~x="" y)="" (&~="" shift(int="" i<100;="" n="Math.abs(rnd.nextInt()%200);" (!x.shiftleft(n).equals="" (x.multiply(biginteger.valueof(2l).pow(n))))="" y[]="x.divideAndRemainder(BigInteger.valueOf(2L).pow(n));" y[1].signum()!="0" y[0].subtract(biginteger.one)="" y[0]);="" b="x.shiftRight(n);" (!b.equals(z))="" system.err.println("input="" is="" "+x.tostring(2));="" system.err.println("shift="" "+n);="" system.err.println("divided="" "+z.tostring(2));="" system.err.println("shifted="" "+b.tostring(2));="" (b.tostring().equals(z.tostring()))="" system.err.println("houston,="" we="" have="" a="" problem.");="" (!x.shiftleft(n).shiftright(n).equals(x))="" report("baz="" shiftleft="" shiftright="" right="" divideandremainder(int="" iterations="order<ORDER_SS_BARRETT" size="" reduced_size;="" i<iterations;="" while(x.compareto(biginteger.valueof(3l))="" (!y[0].equals(biginteger.one))="" system.err.println("fail1="" :"+x);="" system.err.println("="" :"+y);="" (!y[1].equals(biginteger.zero))="" system.err.println("fail2="" (!y[0].equals(biginteger.valueof(2)))="" system.err.println("fail3="" report("divideandremainder="" stringconv()="" generic="" string="" conversion.="" byte="" xbytes[]="new" byte[math.abs(rnd.nextint())%100+1];="" rnd.nextbytes(xbytes);="" biginteger(xbytes);="" radix="Character.MIN_RADIX;" character.max_radix;="" radix++)="" result="x.toString(radix);" biginteger(result,="" radix);="" (!test.equals(x))="" system.err.println("biginteger="" tostring:="" "+x);="" system.err.println("test:="" "+test);="" system.err.println(radix);="" conversion="" straddling="" the="" schoenhage="" algorithm="" crossover="" threshold,="" at="" twice="" four="" times="" threshold.="" k++)="" factor="1" k;="" upper="factor" *="" bits_schoenhage_base="" 33;="" lower="upper" 35;="" bits="upper;">= lower; bits--) { for (int i = 0; i < 50; i++) { BigInteger x = BigInteger.ONE.shiftLeft(bits - 1).or(new BigInteger(bits - 2, rnd)); for (int radix = Character.MIN_RADIX; radix < Character.MAX_RADIX; radix++) { String result = x.toString(radix); BigInteger test = new BigInteger(result, radix); if (!test.equals(x)) { failCount++; System.err.println("BigInteger toString: " + x); System.err.println("Test: " + test); System.err.println(radix); } } } } } report("String Conversion", failCount); } public static void byteArrayConv(int order) { int failCount = 0; for (int i=0; i<size; 2="" 13466917="" 1999999873="" i++)="" {="" biginteger="" x="fetchNumber(order);" while="" (x.equals(biginteger.zero))="" y="new" biginteger(x.tobytearray());="" if="" (!x.equals(y))="" failcount++;="" system.err.println("orig="" is="" "+x);="" system.err.println("new="" "+y);="" }="" report("array="" conversion="" for="" "="" +="" order="" bits",="" failcount);="" public="" static="" void="" modinv(int="" order)="" int="" failcount="0," successcount="0," noninvcount="0;" iterations="order<ORDER_SS_BARRETT" ?="" size="" :="" reduced_size;="" (int="" i="0;" i<iterations;="" while(x.equals(biginteger.zero))="" m="fetchNumber(order).abs();" while(m.compareto(biginteger.one)="" !="1)" try="" inv="x.modInverse(m);" prod="inv.multiply(x).remainder(m);" (prod.signum()="=" -1)="" (prod.equals(biginteger.one))="" successcount++;="" else="" catch(arithmeticexception="" e)="" noninvcount++;="" report("modular="" inverse="" modexp(int="" order1,="" order2)="" i<size="" 10;="" base="fetchNumber(order2);" exp="fetchNumber(8).abs();" z="base.modPow(exp," m);="" w="base.pow(exp.intValue()).mod(m);" (!z.equals(w))="" system.err.println("z="" "+z);="" system.err.println("w="" "+w);="" system.err.println("mod="" "+m);="" system.err.println("base="" "+base);="" system.err.println("exp="" "+exp);="" report("exponentiation="" order1="" and="" order2="" this="" test="" based="" on="" fermat's="" theorem="" which="" not="" ideal="" because="" must="" be="" multiple="" of="" modulus="" a="" prime="" or="" pseudoprime="" (carmichael="" number)="" modexp2(int="" i<10;="" biginteger(100,="" 5,="" rnd);="" while(base.compareto(m)="" while(base.equals(biginteger.zero))="" one="base.modPow(exp," (!one.equals(biginteger.one))="" system.err.println("m="" ii="" private="" final="" int[]="" mersenne_powers="{" 521,="" 607,="" 1279,="" 2203,="" 2281,="" 3217,="" 4253,="" 4423,="" 9689,="" 9941,="" 11213,="" 19937,="" 21701,="" 23209,="" 44497,="" 86243,="" 110503,="" 132049,="" 216091,="" 756839,="" 859433,="" 1257787,="" 1398269,="" 2976221,="" 3021377,="" 6972593,="" };="" long[]="" carmichaels="{" 561,1105,1729,2465,2821,6601,8911,10585,15841,29341,41041,46657,52633,="" 62745,63973,75361,101101,115921,126217,162401,172081,188461,252601,="" 278545,294409,314821,334153,340561,399001,410041,449065,488881,512461,="" 225593397919l="" note:="" testing="" the="" larger="" ones="" takes="" too="" long.="" num_mersennes_to_test="7;" constant="" used="" computed="" carmichaels,="" array="" above="" num_carmichaels_to_test="5;" string[]="" customer_primes="{" "120000000000000000000000000000000019",="" "633825300114114700748351603131",="" "1461501637330902918203684832716283019651637554291",="" "779626057591079617852292862756047675913380626199",="" "857591696176672809403750477631580323575362410491",="" "910409242326391377348778281801166102059139832131",="" "929857869954035706722619989283358182285540127919",="" "961301750640481375785983980066592002055764391999",="" "1267617700951005189537696547196156120148404630231",="" "1326015641149969955786344600146607663033642528339"="" zero="BigInteger.ZERO;" two="new" biginteger("2");="" six="new" biginteger("6");="" twelve="new" biginteger("12");="" eighteen="new" biginteger("18");="" prime()="" p1,="" p2,="" c1;="" consistency="" for(int="" p1="BigInteger.probablePrime(100," (!p1.isprobableprime(100))="" system.err.println("consistency="" "+p1.tostring(16));="" some="" known="" mersenne="" primes="" (2^n)-1="" holds="" exponents,="" numbers="" being="" tested="" i<num_mersennes_to_test;="" system.err.println("mersenne="" "+i+="" failed.");="" reported="" by="" customers="" as="" failing="" in="" past="" i<customer_primes.length;="" biginteger(customer_primes[i]);="" system.err.println("customer="" carmichael="" numbers.="" i<carmichaels.length;="" c1="BigInteger.valueOf(carmichaels[i]);" if(c1.isprobableprime(100))="" system.err.println("carmichael="" prime.");="" form="" (6k+1)(12k+1)(18k+1)="" are="" each="" factors="" found="0;" f1="new" biginteger(40,="" 100,="" (found="" <="" num_carmichaels_to_test)="" k="null;" f2,="" f3;="" biginteger[]="" result="f1.subtract(ONE).divideAndRemainder(SIX);" (result[1].equals(zero))="" f2="k.multiply(TWELVE).add(ONE);" (f2.isprobableprime(100))="" f3="k.multiply(EIGHTEEN).add(ONE);" (f3.isprobableprime(100))="" (c1.isprobableprime(100))="" system.err.println("computed="" +c1.tostring(16));="" found++;="" composites="" that="" products="" i<50;="" p2="BigInteger.probablePrime(100," system.err.println("composite="" failed="" "+c1.tostring(16));="" i<4;="" report("prime",="" primesto100="{" 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97="" aprimesequence="{" 1999999003l,="" 1999999013l,="" 1999999049l,="" 1999999061l,="" 1999999081l,="" 1999999087l,="" 1999999093l,="" 1999999097l,="" 1999999117l,="" 1999999121l,="" 1999999151l,="" 1999999171l,="" 1999999207l,="" 1999999219l,="" 1999999271l,="" 1999999321l,="" 1999999373l,="" 1999999423l,="" 1999999439l,="" 1999999499l,="" 1999999553l,="" 1999999559l,="" 1999999571l,="" 1999999609l,="" 1999999613l,="" 1999999621l,="" 1999999643l,="" 1999999649l,="" 1999999657l,="" 1999999747l,="" 1999999763l,="" 1999999777l,="" 1999999811l,="" 1999999817l,="" 1999999829l,="" 1999999853l,="" 1999999861l,="" 1999999871l,="" nextprobableprime()="" throws="" exception="" p3;="" =="" p3="ZERO;" first="" nextprobableprime="" low="" range="" starting="" at="" i<primesto100.length;="" (p1.longvalue()="" system.err.println("low="" failed");="" system.err.println("p1="" "+p1);="" system.err.println("expected="" "+primesto100[i]);="" relatively="" small,="" sequence="" i<aprimesequence.length;="" system.err.println("prime="" next,="" pick="" large="" primes,="" use="" to="" find="" next="" one,="" make="" sure="" there="" no="" between="" i<100;="" i+="10)" i,="" while(p2.compareto(p3)="" 0)="" (p2.isprobableprime(100)){="" system.err.println("nextprobableprime="" system.err.println("along="" system.err.println("to="" "+p3.tostring(16));="" break;="" report("nextprobableprime",="" serialize()="" string="" bitpatterns[]="{" "ffffffff00000000ffffffff00000000ffffffff00000000",="" "ffffffffffffffffffffffff000000000000000000000000",="" "ffffffff0000000000000000000000000000000000000000",="" "10000000ffffffffffffffffffffffffffffffffffffffff",="" "100000000000000000000000000000000000000000000000",="" "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",="" "-ffffffff00000000ffffffff00000000ffffffff00000000",="" "-ffffffffffffffffffffffff000000000000000000000000",="" "-ffffffff0000000000000000000000000000000000000000",="" "-10000000ffffffffffffffffffffffffffffffffffffffff",="" "-100000000000000000000000000000000000000000000000",="" "-aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"="" bitpatterns.length;="" b1="new" biginteger(bitpatterns[i],="" 16);="" b2="null;" file="" f="new" file("serialtest");="" (fileoutputstream="" fos="new" fileoutputstream(f))="" (objectoutputstream="" oos="new" objectoutputstream(fos))="" oos.writeobject(b1);="" oos.flush();="" (fileinputstream="" fis="new" fileinputstream(f);="" objectinputstream="" ois="new" objectinputstream(fis))="" (!b1.equals(b2)="" ||="" !b1.equals(b1.or(b2)))="" system.err.println("serialized="" hex="" b1.tostring(16));="" f.delete();="" report("serialize",="" **="" *="" main="" interpret="" arguments="" run="" several="" tests.="" up="" three="" may="" given="" specify="" bigintegers="" call="" parameters="" 1,="" 2,="" 3.="" interpreted="" maximum="" number="" decimal="" digits="" will="" have.="" main(string[]="" args)="" variables="" sizing="" bits="" order3="ORDER_KARATSUBA;" order4="ORDER_TOOM_COOK;" order5="ORDER_SS_BARRETT;" (args.length="">0) order1 = (int)((Integer.parseInt(args[0]))* 3.333); if (args.length >1) order2 = (int)((Integer.parseInt(args[1]))* 3.333); if (args.length >2) order3 = (int)((Integer.parseInt(args[2]))* 3.333); if (args.length >3) order4 = (int)((Integer.parseInt(args[3]))* 3.333); if (args.length >4) order5 = (int)((Integer.parseInt(args[4]))* 3.333); prime(); nextProbablePrime(); schoenhageStrassen(order5); inverse(); arithmetic(order1); // small numbers arithmetic(order3); // Karatsuba range arithmetic(order4); // Toom-Cook / Burnikel-Ziegler range arithmetic(order5); // SS/Barrett range divideAndRemainder(order1); // small numbers divideAndRemainder(order3); // Karatsuba range divideAndRemainder(order4); // Toom-Cook / Burnikel-Ziegler range divideAndRemainder(order5); // SS/Barrett range pow(order1); pow(order3); pow(order4); square(ORDER_MEDIUM); square(ORDER_KARATSUBA_SQUARE); square(ORDER_TOOM_COOK_SQUARE); square(order5); // SS/Barrett range bitCount(); bitLength(); bitOps(order1); bitwise(order1); shift(order1); byteArrayConv(order1); modInv(order1); // small numbers modInv(order3); // Karatsuba range modInv(order4); // Toom-Cook / Burnikel-Ziegler range modExp(order1, order2); modExp2(order1); stringConv(); serialize(); multiplyLarge(); squareLarge(); divideLarge(); if (failure) throw new RuntimeException("Failure in BigIntegerTest."); } /* * Get a random or boundary-case number. This is designed to provide * a lot of numbers that will find failure points, such as max sized * numbers, empty BigIntegers, etc. * * If order is less than 2, order is changed to 2. */ private static BigInteger fetchNumber(int order) { boolean negative = rnd.nextBoolean(); int numType = rnd.nextInt(7); BigInteger result = null; if (order < 2) order = 2; switch (numType) { case 0: // Empty result = BigInteger.ZERO; break; case 1: // One result = BigInteger.ONE; break; case 2: // All bits set in number int numBytes = (order+7)/8; byte[] fullBits = new byte[numBytes]; for(int i=0; i<numbytes; i++)="" fullbits[i]="(byte)0xff;" int="" excessbits="8*numBytes" -="" order;="" fullbits[0]="" &="(1" <<="" (8-excessbits))="" 1;="" result="new" biginteger(1,="" fullbits);="" break;="" case="" 3:="" one="" bit="" in="" number="" 4:="" random="" density="" byte[]="" val="new" byte[(order+7)="" 8];="" iterations="rnd.nextInt(order);" for="" (int="" i="0;" i<iterations;="" {="" bitidx="rnd.nextInt(order);" val[bitidx="" 8]="" |="1" (bitidx%8);="" }="" val);="" 5:="" runs="" of="" consecutive="" ones="" and="" zeros="" remaining="order;" while="" (remaining=""> 0) { int runLength = Math.min(remaining, rnd.nextInt(order)); result = result.shiftLeft(runLength); if (bit > 0) result = result.add(ONE.shiftLeft(runLength).subtract(ONE)); remaining -= runLength; bit = 1 - bit; } break; default: // random bits result = new BigInteger(order, rnd); } if (negative) result = result.negate(); return result; } static void report(String testName, int failCount) { System.err.println(testName+": " + (failCount==0 ? "Passed":"Failed("+failCount+")")); if (failCount > 0) failure = true; } } </numbytes;></size;></size*10;></size*10;></reduced_size;></longdigits.length;></a.length;></numbits);></n)></a.length;></size;></size;></size;></size;>