Tag Archive for 'BigInteger'

The problem 97 of Project Euler required one to find the value of:

284332^7830457+1.

Anshumali Srivastava and I spent a lot of time on time, trying to factor the expression into smaller numbers which could make the computation easier. We tried a few things but got stuck every time.

Finally giving up on it, I decided to brute force it using the BigInteger class of Java. Amazingly, it took just a few seconds to get the answer. Looking at the solutions posted in the forum I realized that everyone had done the same and even the Project Euler admin called this one as a freebie. There was one suggestion to improve the solution. You can read about it here:

http://www.osix.net/modules/article/?id=696

The Java implementation for the same would be:

    public static final BigInteger TWO = BigInteger.valueOf(2);

    /**
     * Computes the value of a^b mod c
     *
     * @param a The base
     * @param b The exponent
     * @param c The mod number
     * @return The value of a^b mod c
     */
    public static final BigInteger aPowbModc(BigInteger a, BigInteger b, BigInteger c) {
        long longValue = b.longValue();
        if (longValue < 0) throw new IllegalArgumentException("Exponent should be non negative");
        if (longValue == 0) return BigInteger.ONE;
        if (a.longValue() == 0) return BigInteger.ZERO;

        BigInteger v = NumberUtil.aPowbModc(a, b.divide(NumberUtil.TWO), c).modPow(NumberUtil.TWO, c);

        return longValue % 2 == 1 ? v.multiply(a).mod(c) : v;
    }

The recursive exponentiation function:

    public static BigInteger getVal() {
        BigInteger mod = new BigInteger("10").pow(10);
        BigInteger val = NumberUtil.aPowbModc(new BigInteger("2"), new BigInteger("7830457"), mod)
                .multiply(new BigInteger("28433")).add(BigInteger.ONE);
        return val.mod(mod);
    }

Popularity: 5% [?]