Оптимизировать арифметические операции над очень большими числами

Question

Я хочу, чтобы вычислить функцию Н (п) где

H(0)=0; 
H(i)=H(i-1)×A+Ci mod B; 

10<=A,B<=10^15; 

C представляет собой массив из п элементов

Следующий код занимает слишком много времени ... любой лучший способ сделать это?

public BigInteger H(int no) {    
    if(no>0) { 
     bi=H(no-1); 
     bi=bi.multiply(BigInteger.valueOf(A)); 
     bi=bi.add(BigInteger.valueOf(c[no-1])); 
     bi=bi.remainder(BigInteger.valueOf(B)); 
     return bi; 
    } 

    return BigInteger.ZERO; 

}

Answer 1

Да, добро пожаловать в мир BigIntegers.

Одна вещь, которую я помню, что вы можете сделать два пути для этого:

1) медленный путь с BigIntegers 2) быстрый путь с двойными примитивными типами, когда оба аргумента являются менее Max Double.

Это должно немного накачать скорость.

Сообщите нам, как это происходило, и отправляйте сообщения, если сможете. Это действительно интересно.

Answer 2

Попробуйте не используя оставшийся каждый итерация, он использует деление, которое ОЧЕНЬ медленно.

Вы также не должны использовать BigInteger.valueOf() каждую итерацию. Создавайте только A и B как BigIntegers один раз и сохраняйте их, нет необходимости делать это больше раз.

Answer 3

Попробуйте использовать подход с динамическим программированием. Вместо того, чтобы использовать рекурсию, цикл начинается с начального случая H (0) и перемещается оттуда. Пример:

public static BigInteger H(BigInteger[] c, int no, BigInteger A, BigInteger B) { 

    if (c.length < no - 1) { 
     throw new IllegalArgumentException("no is too large"); 
    } 

    BigInteger bi = BigInteger.ZERO; // Initial case H(0) = 0 

    for (int i = 1; i <= no; i++) { // From H(1) -> H(no) 
     bi = bi.multiply(A).add(c[i - 1]).remainder(B); 
    } 

    return bi; 
}