Разделение цифр BigIntegers

Question

Я пытаюсь разбить цифры целого числа. Позвольте мне быть более конкретным. Я использую последовательность Фибоначчи для генерации большого целого числа, теперь используя этот алгоритм, мне нужно зациклиться до тех пор, пока не найду BigInteger, где первые 9 цифр и последние 9 цифр являются pandigital. Единственная проблема - это сумма, которую я должен зацикливать - 300K (теперь BigInteger будет настолько огромным).

Я попытался преобразовать BigInteger в строку, а затем использовать «substring (begin, end)». Но это так медленно, потребовалось почти 28 минут, чтобы сделать 100K индексов.

Для этого есть математическое решение, но я не совсем уверен, что это такое, если бы кто-то мог привести меня в правильном направлении, это было бы оценено по достоинству. Примечание. Я не прошу ответа напрямую, просто шаг к поиску правильного ответа.

Вот мой код только в том случае, если вам интересно:

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 цифр (и это, кажется, не слишком медленно). Но у меня возникает проблема с получением девяти цифр.

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 и сохранить их в массиве.
• Вам не нужно использовать внутренний цикл, чтобы проверить наличие pandigitalness. Если вам когда-либо нужно увеличивать ячейку в вашем массиве boolean, то это не pandigital. Кроме того, вы можете досрочно выйти на 0.
• Расчет trailing9digits легко с использованием mod 1000000000
• Вы можете предварительно создать свои константы и хранить их, а не создавать их каждый раз. Ваш путь хорош для примитивов, но не для объектов.

Примечание. Я попытался использовать String вместо остатков, они проработали примерно одинаково. Я включил оба кода.

И, наконец, правильный ответ не в первых 300 000; это около 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; 
    } 
}