分裂BigIntegers數字

Question

我想分裂一個大整數的數字。讓我更具體一點。我正在使用Fibonacci序列生成一個大整數，現在使用這個算法我需要循環，直到找到一個BigInteger，其中前9位數字和最後9位數字是pandigital。唯一的問題是我必須循環的數量是300K（現在BigInteger會非常龐大​​）。

我已經嘗試將BigInteger轉換爲字符串，然後使用「substring（begin，end）」。但是，這太慢了，只花了將近28分鐘來完成10萬個指數。

有一個數學解決方案，但我不完全確定它是什麼，如果有人可以帶領我在正確的方向很多將不勝感激。注意：我不直接要求答案，只是尋找正確答案的一步。

這裏是我的代碼，以防萬一你想知道：

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

Answer 1

好的，我對你的代碼做了一些優化。

• 您的leading9Digits方法不應該返回String，它應該返回一個數字。如果他們願意，可以讓代碼的其他部分將它變成一個字符串。每當代碼循環浪費時，調用BigInteger.pow()。你可以預先計算所有這些10的冪，並將它們存儲在一個數組中。
• 您不必使用內部循環來檢查數字。如果你不得不在你的boolean陣列中增加一個單元兩次，那麼它不是泛數。此外，您可以提早退出0。
• 計算trailing9digits很容易使用mod 1000000000
• 您可以預先創建常量並存儲它們，而不是每次都創建它們。你的方式適用於基元，但不適用於對象。

請注意，我嘗試使用String而不是餘數，他們的工作大致相同。我將它們都包含在你的代碼中。

最後，正確答案不在前30萬;它約爲329,000。在我的機器上運行大約需要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; 
    } 
}