/*

 * 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;

/**

 * 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.

 *

 * Four arguments may be specified which give the number of

 * decimal digits you desire in the four 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        = 80  ints = 2560 bits

    // TOOM_COOK_THRESHOLD        = 240 ints = 7680 bits

    // KARATSUBA_SQUARE_THRESHOLD = 128 ints = 4096 bits

    // TOOM_COOK_SQUARE_THRESHOLD = 216 ints = 6912 bits

    //

    // SCHOENHAGE_BASE_CONVERSION_THRESHOLD = 20 ints = 640 bits

    //

    // BURNIKEL_ZIEGLER_THRESHOLD = 80  ints = 2560 bits

    //

    static final int BITS_KARATSUBA = 2560;

    static final int BITS_TOOM_COOK = 7680;

    static final int BITS_KARATSUBA_SQUARE = 4096;

    static final int BITS_TOOM_COOK_SQUARE = 6912;

    static final int BITS_SCHOENHAGE_BASE = 640;

    static final int BITS_BURNIKEL_ZIEGLER = 2560;

    static final int ORDER_SMALL = 60;

    static final int ORDER_MEDIUM = 100;

    // #bits for testing Karatsuba

    static final int ORDER_KARATSUBA = 2760;

    // #bits for testing Toom-Cook and Burnikel-Ziegler

    static final int ORDER_TOOM_COOK = 8000;

    // #bits for testing Karatsuba squaring

    static final int ORDER_KARATSUBA_SQUARE = 4200;

    // #bits for testing Toom-Cook squaring

    static final int ORDER_TOOM_COOK_SQUARE = 7000;

    static final int SIZE = 1000; // numbers per batch

    static Random rnd = new Random();

    static boolean failure = false;

    public static void pow(int order) {

        int failCount1 = 0;

        for (int i=0; i<SIZE; i++) {

            // Test identity x^power == x*x*x ... *x

            int power = rnd.nextInt(6) + 2;

            BigInteger x = fetchNumber(order);

            BigInteger y = x.pow(power);

            BigInteger z = x;

            for (int j=1; j<power; j++)

                z = z.multiply(x);

            if (!y.equals(z))

                failCount1++;

        }

        report("pow for " + order + " bits", failCount1);

    }

    public static void square(int order) {

        int failCount1 = 0;

        for (int i=0; i<SIZE; i++) {

            // Test identity x^2 == x*x

            BigInteger x  = fetchNumber(order);

            BigInteger xx = x.multiply(x);

            BigInteger x2 = x.pow(2);

            if (!x2.equals(xx))

                failCount1++;

        }

        report("square for " + order + " bits", failCount1);

    }

    public static void arithmetic(int order) {

        int failCount = 0;

        for (int i=0; i<SIZE; i++) {

            BigInteger x = fetchNumber(order);

            while(x.compareTo(BigInteger.ZERO) != 1)

                x = fetchNumber(order);

            BigInteger y = fetchNumber(order/2);

            while(x.compareTo(y) == -1)

                y = fetchNumber(order/2);

            if (y.equals(BigInteger.ZERO))

                y = y.add(BigInteger.ONE);

            // Test identity ((x/y))*y + x%y - x == 0

            // using separate divide() and remainder()

            BigInteger baz = x.divide(y);

            baz = baz.multiply(y);

            baz = baz.add(x.remainder(y));

            baz = baz.subtract(x);

            if (!baz.equals(BigInteger.ZERO))

                failCount++;

        }

        report("Arithmetic I for " + order + " bits", failCount);

        failCount = 0;

        for (int i=0; i<100; i++) {

            BigInteger x = fetchNumber(order);

            while(x.compareTo(BigInteger.ZERO) != 1)

                x = fetchNumber(order);

            BigInteger y = fetchNumber(order/2);

            while(x.compareTo(y) == -1)

                y = fetchNumber(order/2);

            if (y.equals(BigInteger.ZERO))

                y = y.add(BigInteger.ONE);

            // Test identity ((x/y))*y + x%y - x == 0

            // using divideAndRemainder()

            BigInteger baz[] = x.divideAndRemainder(y);

            baz[0] = baz[0].multiply(y);

            baz[0] = baz[0].add(baz[1]);

            baz[0] = baz[0].subtract(x);

            if (!baz[0].equals(BigInteger.ZERO))

                failCount++;

        }

        report("Arithmetic II for " + order + " bits", failCount);

    }

    /**

     * Sanity test for Karatsuba and 3-way Toom-Cook multiplication.

     * For each of the Karatsuba and 3-way Toom-Cook multiplication thresholds,

     * construct two factors each with a mag array one element shorter than the

     * threshold, and with the most significant bit set and the rest of the bits

     * random. Each of these numbers will therefore be below the threshold but

     * if shifted left be above the threshold. Call the numbers 'u' and 'v' and

     * define random shifts 'a' and 'b' in the range [1,32]. Then we have the

     * identity

     * <pre>

     * (u << a)*(v << b) = (u*v) << (a + b)

     * </pre>

     * 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; i++) {

            BigInteger x = fetchNumber(BITS_KARATSUBA - 32 - 1);

            BigInteger u = base.add(x);

            int a = 1 + rnd.nextInt(31);

            BigInteger w = u.shiftLeft(a);

            BigInteger y = fetchNumber(BITS_KARATSUBA - 32 - 1);

            BigInteger v = base.add(y);

            int b = 1 + rnd.nextInt(32);

            BigInteger z = v.shiftLeft(b);

            BigInteger multiplyResult = u.multiply(v).shiftLeft(a + b);

            BigInteger 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; i++) {

            BigInteger x = fetchNumber(BITS_TOOM_COOK - 32 - 1);

            BigInteger u = base.add(x);

            BigInteger u2 = u.shiftLeft(1);

            BigInteger y = fetchNumber(BITS_TOOM_COOK - 32 - 1);

            BigInteger v = base.add(y);

            BigInteger v2 = v.shiftLeft(1);

            BigInteger multiplyResult = u.multiply(v).shiftLeft(2);

            BigInteger toomCookMultiplyResult = u2.multiply(v2);

            if (!multiplyResult.equals(toomCookMultiplyResult)) {

                failCount++;

            }

        }

        report("multiplyLarge Toom-Cook", failCount);

    }

    /**

     * Sanity test for Karatsuba and 3-way Toom-Cook squaring.

     * This test is analogous to {@link AbstractMethodError#multiplyLarge}

     * with both factors being equal. The squaring methods will not be tested

     * unless the <code>bigInteger.multiply(bigInteger)</code> tests whether

     * the parameter is the same instance on which the method is being invoked

     * and calls <code>square()</code> accordingly.

     */

    public static void squareLarge() {

        int failCount = 0;

        BigInteger base = BigInteger.ONE.shiftLeft(BITS_KARATSUBA_SQUARE - 32 - 1);

        for (int i=0; i<SIZE; i++) {

            BigInteger x = fetchNumber(BITS_KARATSUBA_SQUARE - 32 - 1);

            BigInteger u = base.add(x);

            int a = 1 + rnd.nextInt(31);

            BigInteger w = u.shiftLeft(a);

            BigInteger squareResult = u.multiply(u).shiftLeft(2*a);

            BigInteger 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; i++) {

            BigInteger x = fetchNumber(BITS_TOOM_COOK_SQUARE - 32 - 1);

            BigInteger u = base.add(x);

            int a = 1 + rnd.nextInt(31);

            BigInteger w = u.shiftLeft(a);

            BigInteger squareResult = u.multiply(u).shiftLeft(2*a);

            BigInteger toomCookSquareResult = w.multiply(w);

            if (!squareResult.equals(toomCookSquareResult)) {

                failCount++;

            }

        }

        report("squareLarge Toom-Cook", failCount);

    }

    /**

     * Sanity test for Burnikel-Ziegler division.  The Burnikel-Ziegler division

     * algorithm is used when each of the dividend and the divisor has at least

     * a specified number of ints in its representation.  This test is based on

     * the observation that if {@code w = u*pow(2,a)} and {@code z = v*pow(2,b)}

     * where {@code 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);

            BigInteger v = base.add(addend);

            BigInteger u = v.multiply(BigInteger.valueOf(2 + rnd.nextInt(Short.MAX_VALUE - 1)));

            if(rnd.nextBoolean()) {

                u = u.negate();

            }

            if(rnd.nextBoolean()) {

                v = v.negate();

            }

            int a = 17 + rnd.nextInt(16);

            int b = 1 + rnd.nextInt(16);

            BigInteger w = u.multiply(BigInteger.valueOf(1L << a));

            BigInteger 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 << b));

            BigInteger[] bzResult = w.divideAndRemainder(z);

            if (divideResult[0].compareTo(bzResult[0]) != 0 ||

                    divideResult[1].compareTo(bzResult[1]) != 0) {

                failCount++;

            }

        }

        report("divideLarge", failCount);

    }

    public static void bitCount() {

        int failCount = 0;

        for (int i=0; i<SIZE*10; i++) {

            int x = rnd.nextInt();

            BigInteger bigX = BigInteger.valueOf((long)x);

            int bit = (x < 0 ? 0 : 1);

            int tmp = x, bitCount = 0;

            for (int j=0; j<32; j++) {

                bitCount += ((tmp & 1) == bit ? 1 : 0);

                tmp >>= 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; i++) {

            int x = rnd.nextInt();

            BigInteger bigX = BigInteger.valueOf((long)x);

            int signBit = (x < 0 ? 0x80000000 : 0);

            int tmp = x, bitLength, j;

            for (j=0; j<32 && (tmp & 0x80000000)==signBit; j++)

                tmp <<= 1;

            bitLength = 32 - j;

            if (bigX.bitLength() != bitLength) {

                //System.err.println(x+": "+bitLength+", "+bigX.bitLength());

                failCount++;

            }

        }

        report("BitLength", failCount);

    }

    public static void bitOps(int order) {

        int failCount1 = 0, failCount2 = 0, failCount3 = 0;

        for (int i=0; i<SIZE*5; i++) {

            BigInteger x = fetchNumber(order);

            BigInteger y;

            // Test setBit and clearBit (and testBit)

            if (x.signum() < 0) {

                y = BigInteger.valueOf(-1);

                for (int j=0; j<x.bitLength(); j++)

                    if (!x.testBit(j))

                        y = y.clearBit(j);

            } else {

                y = BigInteger.ZERO;

                for (int j=0; j<x.bitLength(); j++)

                    if (x.testBit(j))

                        y = y.setBit(j);

            }

            if (!x.equals(y))

                failCount1++;

            // Test flipBit (and testBit)

            y = BigInteger.valueOf(x.signum()<0 ? -1 : 0);

            for (int j=0; j<x.bitLength(); j++)

                if (x.signum()<0  ^  x.testBit(j))

                    y = y.flipBit(j);

            if (!x.equals(y))

                failCount2++;

        }

        report("clearBit/testBit for " + order + " bits", failCount1);

        report("flipBit/testBit for " + order + " bits", failCount2);

        for (int i=0; i<SIZE*5; i++) {

            BigInteger x = fetchNumber(order);

            // Test getLowestSetBit()

            int k = x.getLowestSetBit();

            if (x.signum() == 0) {

                if (k != -1)

                    failCount3++;

            } else {

                BigInteger z = x.and(x.negate());

                int j;

                for (j=0; j<z.bitLength() && !z.testBit(j); j++)

                    ;

                if (k != j)

                    failCount3++;

            }

        }

        report("getLowestSetBit for " + order + " bits", failCount3);

    }

    public static void bitwise(int order) {

        // Test identity x^y == x|y &~ x&y

        int failCount = 0;

        for (int i=0; i<SIZE; i++) {

            BigInteger x = fetchNumber(order);

            BigInteger y = fetchNumber(order);

            BigInteger z = x.xor(y);

            BigInteger w = x.or(y).andNot(x.and(y));

            if (!z.equals(w))

                failCount++;

        }

        report("Logic (^ | & ~) for " + order + " bits", failCount);

        // Test identity x &~ y == ~(~x | y)

        failCount = 0;

        for (int i=0; i<SIZE; i++) {

            BigInteger x = fetchNumber(order);

            BigInteger y = fetchNumber(order);

            BigInteger z = x.andNot(y);

            BigInteger w = x.not().or(y).not();

            if (!z.equals(w))

                failCount++;

        }

        report("Logic (&~ | ~) for " + order + " bits", failCount);

    }

    public static void shift(int order) {

        int failCount1 = 0;

        int failCount2 = 0;

        int failCount3 = 0;

        for (int i=0; i<100; i++) {

            BigInteger x = fetchNumber(order);

            int n = Math.abs(rnd.nextInt()%200);

            if (!x.shiftLeft(n).equals

                (x.multiply(BigInteger.valueOf(2L).pow(n))))

                failCount1++;

            BigInteger y[] =x.divideAndRemainder(BigInteger.valueOf(2L).pow(n));

            BigInteger z = (x.signum()<0 && y[1].signum()!=0

                            ? y[0].subtract(BigInteger.ONE)

                            : y[0]);

            BigInteger b = x.shiftRight(n);

            if (!b.equals(z)) {

                System.err.println("Input is "+x.toString(2));

                System.err.println("shift is "+n);

                System.err.println("Divided "+z.toString(2));

                System.err.println("Shifted is "+b.toString(2));

                if (b.toString().equals(z.toString()))

                    System.err.println("Houston, we have a problem.");

                failCount2++;

            }

            if (!x.shiftLeft(n).shiftRight(n).equals(x))

                failCount3++;

        }

        report("baz shiftLeft for " + order + " bits", failCount1);

        report("baz shiftRight for " + order + " bits", failCount2);

        report("baz shiftLeft/Right for " + order + " bits", failCount3);

    }

    public static void divideAndRemainder(int order) {

        int failCount1 = 0;

        for (int i=0; i<SIZE; i++) {

            BigInteger x = fetchNumber(order).abs();

            while(x.compareTo(BigInteger.valueOf(3L)) != 1)

                x = fetchNumber(order).abs();