Самый быстрый способ вычисления (n + 1)^j из (n^j)

Question

Мне нужно вычислить 0^j, 1^j, ..., k^j для некоторых очень больших k и j (оба в порядка нескольких миллионов). Я использую GMP для обработки больших целых чисел (да, мне нужны целые числа, поскольку мне нужна полная точность). Теперь, интересно, как только я попытаюсь вычислить n^j, нет ли способа ускорить вычисление (n + 1)^j вместо того, чтобы начинать с нуля?

Вот алгоритм я в настоящее время использую, чтобы вычислить мощность:

mpz_class pow(unsigned long int b, unsigned long int e) 
{ 
    mpz_class res = 1; 
    mpz_class m = b; 

    while(e) 
    { 
     if(e & 1) 
     { 
      res *= m; 
     } 

     e >>= 1; 
     m *= m; 
    } 

    return res; 
} 

Как вы можете видеть, каждый раз, когда я начинаю с нуля, и это занимает много времени.

Answer 1

Чтобы вычислить n^j, почему бы не найти хотя бы один из факторов по n, скажем k выполнить n^j = k^j * (n/k)^j? К моменту вычисления n^j должны быть известны как k^j, так и (n/k)^j.

Однако вышеуказанное имеет потенциально O(sqrt(n)) время для n. У нас есть вычисление n^j независимо от O(log(j)) времени на Exponentiation by Squaring, как вы уже упоминали в коде выше.

Таким образом, вы могли бы иметь сочетание выше в зависимости от того, который больше:

1. Если n гораздо меньше log(j), вычислить n^j факторизацией.

2. Когда n^j известен как {(2*n)^j, (3*n)^j, ..., ((n-1)*n)^j, n * n^j} и держит его в таблице поиска.

3. Если n больше log(j), и готовое вычисление, как указано выше, невозможно, используйте логарифмический метод, а затем вычислите другие связанные полномочия, как указано выше.

4. Если n является чистой силой 2 (возможно const time computation), вычислить j й степени путем сдвига и расчет соответствующих сумм.

5. Если значение n равно (вычисление константного времени), используйте метод факторизации и вычислите связанные продукты.

Вышеприведенное должно сделать это довольно быстро. Например, идентификация четных чисел сама по себе должна преобразовать половину вычислений мощности в умножения. Можно было бы найти много других правил большого пальца, которые могли бы быть найдены в отношении факторизации, которые могли бы дополнительно уменьшить вычисление (особенно для делимости на 3, 7 и т. Д.)

Answer 2

Вы можете использовать биномиальное разложение (n + 1)^j при n^j + j n^(j-1) + j (j-1)/2 * n^(j- 2) + ... + 1 и memoize нижние мощности, уже вычисленные и повторно используемые для вычисления (n + 1)^j в O (n) времени путем добавления. Если вы вычисляете коэффициенты j, j * (j-1)/2, ... поэтапно, добавляя каждое слагаемое, это можно сделать и в O (n).