Mercurial > jdk8-mips64-public > jdk / changeset

     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/test/java/math/BigInteger/PrimeTest.java	Wed May 07 11:45:31 2014 -0700
     1.3 @@ -0,0 +1,196 @@
     1.4 +/*
     1.5 + * Copyright (c) 2014, Oracle and/or its affiliates. All rights reserved.
     1.6 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
     1.7 + *
     1.8 + * This code is free software; you can redistribute it and/or modify it
     1.9 + * under the terms of the GNU General Public License version 2 only, as
    1.10 + * published by the Free Software Foundation.  Oracle designates this
    1.11 + * particular file as subject to the "Classpath" exception as provided
    1.12 + * by Oracle in the LICENSE file that accompanied this code.
    1.13 + *
    1.14 + * This code is distributed in the hope that it will be useful, but WITHOUT
    1.15 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
    1.16 + * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
    1.17 + * version 2 for more details (a copy is included in the LICENSE file that
    1.18 + * accompanied this code).
    1.19 + *
    1.20 + * You should have received a copy of the GNU General Public License version
    1.21 + * 2 along with this work; if not, write to the Free Software Foundation,
    1.22 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
    1.23 + *
    1.24 + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
    1.25 + * or visit www.oracle.com if you need additional information or have any
    1.26 + * questions.
    1.27 + */
    1.28 +
    1.29 +/*
    1.30 + * @test
    1.31 + * @bug 8026236
    1.32 + * @summary test primality verification methods in BigInteger
    1.33 + * @author bpb
    1.34 + */
    1.35 +import java.math.BigInteger;
    1.36 +import java.util.BitSet;
    1.37 +import java.util.List;
    1.38 +import java.util.NavigableSet;
    1.39 +import java.util.SplittableRandom;
    1.40 +import java.util.TreeSet;
    1.41 +import static java.util.stream.Collectors.toCollection;
    1.42 +import static java.util.stream.Collectors.toList;
    1.43 +import java.util.stream.IntStream;
    1.44 +import java.util.stream.Stream;
    1.45 +
    1.46 +public class PrimeTest {
    1.47 +
    1.48 +    private static final int DEFAULT_UPPER_BOUND = 1299709; // 100000th prime
    1.49 +    private static final int DEFAULT_CERTAINTY = 100;
    1.50 +    private static final int NUM_NON_PRIMES = 10000;
    1.51 +
    1.52 +    /**
    1.53 +     * Run the test.
    1.54 +     *
    1.55 +     * @param args The parameters.
    1.56 +     * @throws Exception on failure
    1.57 +     */
    1.58 +    public static void main(String[] args) throws Exception {
    1.59 +        // Prepare arguments
    1.60 +        int upperBound = args.length > 0 ? Integer.valueOf(args[0]) : DEFAULT_UPPER_BOUND;
    1.61 +        int certainty = args.length > 1 ? Integer.valueOf(args[1]) : DEFAULT_CERTAINTY;
    1.62 +        boolean parallel = args.length > 2 ? Boolean.valueOf(args[2]) : true;
    1.63 +
    1.64 +        // Echo parameter settings
    1.65 +        System.out.println("Upper bound = " + upperBound
    1.66 +                + "\nCertainty = " + certainty
    1.67 +                + "\nParallel = " + parallel);
    1.68 +
    1.69 +        // Get primes through specified bound (inclusive) and Integer.MAX_VALUE
    1.70 +        NavigableSet<BigInteger> primes = getPrimes(upperBound);
    1.71 +
    1.72 +        // Check whether known primes are identified as such
    1.73 +        boolean primeTest = checkPrime(primes, certainty, parallel);
    1.74 +        System.out.println("Prime test result: " + (primeTest ? "SUCCESS" : "FAILURE"));
    1.75 +        if (!primeTest) {
    1.76 +            System.err.println("Prime test failed");
    1.77 +        }
    1.78 +
    1.79 +        // Check whether known non-primes are not identified as primes
    1.80 +        boolean nonPrimeTest = checkNonPrime(primes, certainty);
    1.81 +        System.out.println("Non-prime test result: " + (nonPrimeTest ? "SUCCESS" : "FAILURE"));
    1.82 +
    1.83 +        if (!primeTest || !nonPrimeTest) {
    1.84 +            throw new Exception("PrimeTest FAILED!");
    1.85 +        }
    1.86 +
    1.87 +        System.out.println("PrimeTest succeeded!");
    1.88 +    }
    1.89 +
    1.90 +    /**
    1.91 +     * Create a {@code BitSet} wherein a set bit indicates the corresponding
    1.92 +     * index plus 2 is prime. That is, if bit N is set, then the integer N + 2
    1.93 +     * is prime. The values 0 and 1 are intentionally excluded. See the
    1.94 +     * <a
    1.95 +     * href="http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Algorithm_description">
    1.96 +     * Sieve of Eratosthenes</a> algorithm description for more information.
    1.97 +     *
    1.98 +     * @param upperBound The maximum prime to allow
    1.99 +     * @return bits indicating which indexes represent primes
   1.100 +     */
   1.101 +    private static BitSet createPrimes(int upperBound) {
   1.102 +        int nbits = upperBound - 1;
   1.103 +        BitSet bs = new BitSet(nbits);
   1.104 +        for (int p = 2; p * p < upperBound;) {
   1.105 +            for (int i = p * p; i < nbits + 2; i += p) {
   1.106 +                bs.set(i - 2, true);
   1.107 +            }
   1.108 +            do {
   1.109 +                ++p;
   1.110 +            } while (p > 1 && bs.get(p - 2));
   1.111 +        }
   1.112 +        bs.flip(0, nbits);
   1.113 +        return bs;
   1.114 +    }
   1.115 +
   1.116 +    /**
   1.117 +     * Load the primes up to the specified bound (inclusive) into a
   1.118 +     * {@code NavigableSet}, appending the prime {@code Integer.MAX_VALUE}.
   1.119 +     *
   1.120 +     * @param upperBound The maximum prime to allow
   1.121 +     * @return a set of primes
   1.122 +     */
   1.123 +    private static NavigableSet<BigInteger> getPrimes(int upperBound) {
   1.124 +        BitSet bs = createPrimes(upperBound);
   1.125 +        NavigableSet<BigInteger> primes = bs.stream()
   1.126 +                .mapToObj(p -> BigInteger.valueOf(p + 2))
   1.127 +                .collect(toCollection(TreeSet::new));
   1.128 +        primes.add(BigInteger.valueOf(Integer.MAX_VALUE));
   1.129 +        System.out.println(String.format("Created %d primes", primes.size()));
   1.130 +        return primes;
   1.131 +    }
   1.132 +
   1.133 +    /**
   1.134 +     * Verifies whether the fraction of probable primes detected is at least 1 -
   1.135 +     * 1/2^certainty.
   1.136 +     *
   1.137 +     * @return true if and only if the test succeeds
   1.138 +     */
   1.139 +    private static boolean checkPrime(NavigableSet<BigInteger> primes,
   1.140 +            int certainty,
   1.141 +            boolean parallel) {
   1.142 +        long probablePrimes = (parallel ? primes.parallelStream() : primes.stream())
   1.143 +                .filter(bi -> bi.isProbablePrime(certainty))
   1.144 +                .count();
   1.145 +
   1.146 +        // N = certainty / 2
   1.147 +        // Success if p/t >= 1 - 1/4^N
   1.148 +        // or (p/t)*4^N >= 4^N - 1
   1.149 +        // or p*4^N >= t*(4^N - 1)
   1.150 +        BigInteger p = BigInteger.valueOf(probablePrimes);
   1.151 +        BigInteger t = BigInteger.valueOf(primes.size());
   1.152 +        BigInteger fourToTheC = BigInteger.valueOf(4).pow(certainty / 2);
   1.153 +        BigInteger fourToTheCMinusOne = fourToTheC.subtract(BigInteger.ONE);
   1.154 +        BigInteger left = p.multiply(fourToTheC);
   1.155 +        BigInteger right = t.multiply(fourToTheCMinusOne);
   1.156 +
   1.157 +        if (left.compareTo(right) < 0) {
   1.158 +            System.err.println("Probable prime certainty test failed.");
   1.159 +        }
   1.160 +
   1.161 +        return left.compareTo(right) >= 0;
   1.162 +    }
   1.163 +
   1.164 +    /**
   1.165 +     * Verifies whether all {@code BigInteger}s in the tested range for which
   1.166 +     * {@code isProbablePrime()} returns {@code false} are <i>not</i>
   1.167 +     * prime numbers.
   1.168 +     *
   1.169 +     * @return true if and only if the test succeeds
   1.170 +     */
   1.171 +    private static boolean checkNonPrime(NavigableSet<BigInteger> primes,
   1.172 +            int certainty) {
   1.173 +        int maxPrime = DEFAULT_UPPER_BOUND;
   1.174 +        try {
   1.175 +            maxPrime = primes.last().intValueExact();
   1.176 +        } catch (ArithmeticException e) {
   1.177 +            // ignore it
   1.178 +        }
   1.179 +
   1.180 +        // Create a list of non-prime BigIntegers.
   1.181 +        List<BigInteger> nonPrimeBigInts = (new SplittableRandom())
   1.182 +                .ints(NUM_NON_PRIMES, 2, maxPrime).mapToObj(BigInteger::valueOf)
   1.183 +                .filter(b -> !b.isProbablePrime(certainty)).collect(toList());
   1.184 +
   1.185 +        // If there are any non-probable primes also in the primes list then fail.
   1.186 +        boolean failed = nonPrimeBigInts.stream().anyMatch(primes::contains);
   1.187 +
   1.188 +        // In the event, print which purported non-primes were actually prime.
   1.189 +        if (failed) {
   1.190 +            for (BigInteger bigInt : nonPrimeBigInts) {
   1.191 +                if (primes.contains(bigInt)) {
   1.192 +                    System.err.println("Prime value thought to be non-prime: " + bigInt);
   1.193 +                }
   1.194 +            }
   1.195 +        }
   1.196 +
   1.197 +        return !failed;
   1.198 +    }
   1.199 +}