Splitting BigIntegers digits

Question

I am trying to split a big integer's digits. Let me be a bit more specific. I am using the Fibonacci sequence to generate a big integer, now using this algorithm I need to loop until I find a BigInteger where the first 9 digits and the last 9 digits are pandigital. Only problem is the amount I have to loop is 300K (now that BigInteger is going to be so huge).

I have tried converting the BigInteger into a string, and then using "substring(begin, end)." But, that is so slow, it took nearly 28 minutes just to do 100K indexes.

There is a mathematical solution for this, but I am not completely sure what it is, if someone could lead me within the right direction much would be appreciated. Note: I am not asking for the answer directly, just a step towards finding the right answer.

Here is my code just in case you're wondering:

import java.math.BigInteger;

public class Main {

    public static void main(String...strings)
    {       
        long timeStart = System.currentTimeMillis();
        fib(300_000);
        long timeEnd = System.currentTimeMillis();
        System.out.println("Finished processing, time: " + (timeEnd - timeStart) + " milliseconds.");
    }

    public static BigInteger fib(int n)
    {
        BigInteger prev1 = BigInteger.valueOf(0), prev2 = BigInteger.valueOf(1);        
        for (int i = 0; i < n; i++)
        {
            BigInteger savePrev1 = prev1;
            prev1 = prev2;
            prev2 = savePrev1.add(prev2);
        }
        return prev1;
    }

    static BigInteger[] pows = new BigInteger[16];

    static {
        for (int i = 0; i < 16; i++) {
            pows[i] = BigInteger.TEN.pow(i);
        }
    }

    static boolean isPanDigital(BigInteger n) {
         if (!n.remainder(BigInteger.valueOf(9)).equals(BigInteger.ZERO)) {
           return false;
        }
        boolean[] foundDigits = new boolean[9];


        boolean isPanDigital = true;
        for (int i = 1; i <= 9; i++) {
            BigInteger digit = n.remainder(pows[i]).divide(pows[i - 1]);
            for (int j = 0; j < foundDigits.length; j++) {
                if (digit.equals(BigInteger.valueOf(j + 1)) && !foundDigits[j]) {
                    foundDigits[j] = true;
                }
            }
        }

        for (int i = 0; i < 9; i++) {
            isPanDigital = isPanDigital && foundDigits[i];
        }

        return isPanDigital;
    }
}

Updated, managed to figure out how to generate the first 9 digits (and it doesn't seem to be too slow). But, I am having an issue generating the last 9 digits.

import java.math.BigInteger;

public class Main {

    public static void main(String...strings)
    {       
        long timeStart = System.currentTimeMillis();
        fib(300_000);
        long timeEnd = System.currentTimeMillis();
        System.out.println("Finished processing, time: " + (timeEnd - timeStart) + " milliseconds.");
    }

    public static BigInteger fib(int n)
    {
        BigInteger prev1 = BigInteger.valueOf(0), prev2 = BigInteger.valueOf(1);        
        for (int i = 0; i < n; i++)
        {
            if (prev1.toString().length() > 19)
            {
                String leading9Digits = leading9Digits(prev1);
                if (isPanDigital(BigInteger.valueOf(Integer.valueOf(leading9Digits))))
                {
                    System.out.println("Solved at index: " + i);
                    break;
                }
            }
            BigInteger savePrev1 = prev1;
            prev1 = prev2;
            prev2 = savePrev1.add(prev2);
        }
        return prev1;
    }

    public static String leading9Digits(BigInteger x) {
        int log10 = (x.bitLength() - 1) * 3 / 10;
        x = x.divide(BigInteger.TEN.pow(Math.max(log10 + 1 - 9, 0)));
        return x.toString().substring(0, 9);
    }

    static BigInteger[] pows = new BigInteger[16];

    static {
        for (int i = 0; i < 16; i++) {
            pows[i] = BigInteger.TEN.pow(i);
        }
    }

    static boolean isPanDigital(BigInteger n) {
         if (!n.remainder(BigInteger.valueOf(9)).equals(BigInteger.ZERO)) {
           return false;
        }
        boolean[] foundDigits = new boolean[9];


        boolean isPanDigital = true;
        for (int i = 1; i <= 9; i++) {
            BigInteger digit = n.remainder(pows[i]).divide(pows[i - 1]);
            for (int j = 0; j < foundDigits.length; j++) {
                if (digit.equals(BigInteger.valueOf(j + 1)) && !foundDigits[j]) {
                    foundDigits[j] = true;
                }
            }
        }

        for (int i = 0; i < 9; i++) {
            isPanDigital = isPanDigital && foundDigits[i];
        }

        return isPanDigital;
    }
}

Answer 1

Okay, I made a number of optimizations to your code.

• Your leading9Digits method should not return a String, it should return a number. Allow other parts of your code to turn it into a string if they prefer.
• Calling BigInteger.pow() every time the code loops is a waste. You can precalculate all these powers of 10 and store them in an array.
• You don't have to use an inner loop to check for pandigitalness. If you ever have to increment a cell in your boolean array twice, then it's not pandigital. Additionally, you can early exit on a 0.
• Calculating trailing9digits is easy using mod 1000000000
• You can pre-create your constants and store them rather than creating them each time. Your way is fine for primitives but not objects.

Note, I tried using a String instead of remainders, they worked out to be about the same. I included both in your code.

And, finally, the correct answer is not in the first 300,000; it's about 329,000. And it takes about 29 seconds to run on my machine.

import java.math.BigInteger;

public class Main {
    private static final BigInteger NINE = BigInteger.valueOf(9);
    private static final BigInteger BILLION = BigInteger.valueOf(1000000000);
    private static final double log10_2 = Math.log10(2);
    private static final double CORRECTION = 9d;
    private static final int ARRAY_SIZE = 131072;

    static BigInteger[] pows = new BigInteger[ARRAY_SIZE];

    static {
        pows[0] = BigInteger.ONE;
        for (int i = 1; i < ARRAY_SIZE; i++) {
            pows[i] = pows[i - 1].multiply(BigInteger.TEN);
        }
    }

    public static void main(String... strings) {
        long timeStart = System.currentTimeMillis();
        fib(500_000);
        long timeEnd = System.currentTimeMillis();
        System.out.println("Finished processing, time: "
                + (timeEnd - timeStart) + " milliseconds.");
    }

    public static BigInteger fib(int n) {
        BigInteger prev1 = BigInteger.valueOf(0), prev2 = BigInteger.valueOf(1);
        for (int i = 0; i < n; i++) {
            if (prev1.bitLength() > 30) {
                if (isDualPanDigital(prev1)) {
                    System.out.println("Solved at index: " + i);
                    break;
                }
            }
            BigInteger savePrev1 = prev1;
            prev1 = prev2;
            prev2 = savePrev1.add(prev2);
        }
        return prev1;
    }

    public static BigInteger leading9Digits(BigInteger x) {
        int dividePower = (int) (x.bitLength() * log10_2 - CORRECTION);
        BigInteger y = x.divide(pows[dividePower]);
        if (y.compareTo(BILLION) != -1) y = y.divide(BigInteger.TEN);
        return y;
    }

    public static BigInteger trailing9Digits(BigInteger x) {
        return x.mod(BILLION);
    }

    static boolean isDualPanDigital(BigInteger n) {
        boolean leading = isPanDigital(leading9Digits(n));
        boolean trailing = isPanDigital(trailing9Digits(n));

        if (leading && trailing) {
            System.out.format("leadingDigits: %s, trailingDigits: %s%n",
                    leading9Digits(n), trailing9Digits(n));
        }
        return leading && trailing;
    }

    static boolean isPanDigital(BigInteger n) {
        if (!n.remainder(NINE).equals(BigInteger.ZERO)) {
            return false;
        }

        return isPanDigitalString(n);
    }

    private static boolean isPanDigitalMath(BigInteger n) {
        boolean[] foundDigits = new boolean[10];

        for (int i = 1; i <= 9; i++) {
            int digit = n.remainder(pows[i]).divide(pows[i - 1]).intValue();
            if (digit == 0)
                return false;
            if (foundDigits[digit - 1])
                return false;
            else
                foundDigits[digit - 1] = true;
        }

        return true;
    }

    private static boolean isPanDigitalString(BigInteger n) {
        boolean[] foundDigits = new boolean[9];

        String s = n.toString();
        if (s.length() < 9) {
            return false;
        }

        for (int i = 0; i < 9; i++) {
            int digit = s.charAt(i) - '1';
            if (digit == -1 || foundDigits[digit])
                return false;
            foundDigits[digit] = true;
        }

        return true;
    }
}