拆分大整数位数

Question

我正在尝试将一个大整数的数字拆分开。更具体地说，我正在使用斐波那契数列生成一个大整数，现在我需要循环直到找到一个 BigInteger，其中前9位数字和后9位数字是全数字。唯一的问题是我必须循环300K次（BigInteger会变得非常巨大）。

我已经尝试将 BigInteger 转换为字符串，然后使用 "substring(begin, end)"。但是，这太慢了，仅对100K个索引进行操作就需要近28分钟。

有一个数学解决方案，但我不完全确定它是什么，如果有人能帮我指明正确的方向，我将不胜感激。注意：我不是直接要求答案，只是要找到正确答案的一步。

以下是我的代码，以防您想知道：

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

更新了，成功想出如何生成前9位数字（而且速度似乎不太慢）。但是，我遇到了一个问题，无法生成后9位数字。

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

- Thomas Le Godais

---

抱歉，我还不理解：BigInteger.toString() 或 String.substring。你只需要9个符号，这不应该花费太多时间。 - default locale

将这样巨大的 BigIntegers 进行除法运算绝对不是一个好主意。 - default locale

另一个问题是你使用的Fibonacci算法版本也相当低效，获取第45000个序列（即2910856237598579040）只需要1-2秒钟。 - classicjonesynz

这听起来就像是欧拉计划104题。如果是的话，你已经得到了正确的答案。和所有欧拉问题一样，有一个诀窍，也许在计算时你并不需要所有数字？ - Roger Lindsjö

我更新了主贴，我解决了前9个（速度似乎不是太慢）。以类似的方式，我该如何获取最后9位数字？ - Thomas Le Godais

Answer 1

好的，我对您的代码进行了多项优化。

• 您的leading9Digits方法不应该返回一个String，而应该返回一个数字。如果需要，其他部分的代码可以将其转换为字符串。
• 每次循环调用BigInteger.pow()是浪费的。您可以预先计算所有这些10的幂并将它们存储在数组中。
• 您不必使用内部循环来检查是否为全数字。如果您必须在boolean数组中两次递增单元格，则它不是全数字。此外，您可以在出现0时提前退出。
• 使用mod 1000000000可以轻松计算trailing9digits
• 您可以预先创建常量并将它们存储起来，而不是每次都创建它们。对于基本类型，您的方式是可以的，但不适用于对象。

注意，我尝试使用String而不是余数，它们的效果差不多。我在您的代码中包含了两者。

最终，正确答案并不在前三十万个中；它大约在三十二万九千左右。在我的机器上运行需要约29秒。

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

- durron597