Оптимизировать арифметические операции с очень большими числами - PullRequest
Новая
       37

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

3 голосов
/ 08 августа 2010

Я хочу вычислить функцию H (n) где 

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

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

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

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

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;

}

Ответы [ 3 ]

3 голосов
/ 08 августа 2010

Попробуйте использовать подход динамического программирования. Вместо использования рекурсии, цикл начинается с начального случая 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;
}
2 голосов
/ 08 августа 2010

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

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

0 голосов
/ 08 августа 2010

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

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

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

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

Расскажите нам, как все прошло, и опубликуйте время, если можете. Это действительно интересно.

...