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

Мне нужно вычислить 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;
}

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


algorithm pow
person Matteo Monti    schedule 28.01.2017    source источник
comment
Вы должны применять динамическое программирование, начиная с 5^2 = 4^2 + 3^2 ›› Fibonacci , чтобы максимально сократить расчет   -  person Null    schedule 28.01.2017
comment
Я думаю, ты потерял меня...? Можете ли вы уточнить немного больше?   -  person Matteo Monti    schedule 28.01.2017
comment
ты не согласен, что b^e = (b-1)^e + (b-2)^e ?   -  person Null    schedule 28.01.2017
comment
@Null Вы имеете в виду 7 ^ 2 = 6 ^ 2 + 5 ^ 2?   -  person user3386109    schedule 28.01.2017
comment
@Null - пользователь 3386109 предоставил контрпример.   -  person Peter    schedule 28.01.2017
comment
Я предлагаю вам опубликовать этот вопрос на math.stackexchange.com. Программисты, как видите, не очень-то разбираются в математике :)   -  person GOTO 0    schedule 28.01.2017
comment
@Null 5^2 * 4^2 + 3^2, потому что (3, 4, 5) — пифагорейская тройка..   -  person Matteo Monti    schedule 28.01.2017
comment
Пожалуйста, укажите в своем вопросе, какая информация может быть доступна pow() в дополнение к b и e. Если бы это было b**(e-1), это не выглядело бы скучно -?   -  person greybeard    schedule 28.01.2017
comment
Что ж, если бы речь шла о вычислении b^(e - 1) из b^e, я согласен, что это было бы довольно просто, так как сводилось бы к делению на b. Но моя проблема здесь заключается в вычислении (b - 1)^e, показатель степени должен оставаться прежним.   -  person Matteo Monti    schedule 28.01.2017
comment
Я не предлагал вычислять что-то еще. Я прошу указать, какая информация доступна, приведя пример, который сделал бы вопрос спорным. Я так понял, что (b - 1)^e можно было вычислить b^e, а как насчет (b-2)^e, …? Что будет доступно? Будет ли установлен фиксированный лимит на сумму ввода? Думаю, для любого фиксированного j/e будут нетривиальные формулы в меньших степенях.   -  person greybeard    schedule 28.01.2017

Ответы (2)


arrow_upward
1
arrow_downward

Чтобы вычислить 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)) времени с помощью возведения в степень путем возведения в квадрат, как вы упомянули в код выше.

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

  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 (возможно вычисление с постоянным временем), вычислить j-ю степень путем сдвига и вычислить соответствующие суммы.

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

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

person user1952500    schedule 28.01.2017
comment
@greybeard увидел это только сейчас. - person user1952500; 28.01.2017
comment
Красивый. Большое спасибо! - person Matteo Monti; 28.01.2017

arrow_upward
1
arrow_downward

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

person Sandipan Dey    schedule 28.01.2017
comment
Это звучит как отличное решение. К сожалению, это также потребует огромного количества памяти. Для хранения каждого числа в порядке 2000000^2000000 потребуется около 8 MB, а я не могу позволить себе 1 TB или оперативную память... - person Matteo Monti; 28.01.2017
comment
Может быть, тогда мы можем использовать 2 ^ j * ((n + 1)/2) ^ j, когда n нечетно, 2 ^ j можно вычислить просто сдвигом влево. - person Sandipan Dey; 28.01.2017
comment
Что, если у нас тоже есть какие-то дисковые операции, мы тоже собираемся оптимизировать скорость? - person Sandipan Dey; 28.01.2017