Алгоритм на экспоненте с иррациональным основанием

Я знаю, что существует алгоритм O(logn) для вычисления a^n, где a — целое число, а n — огромное целое число (вероятно, результат должен быть модульным другим простым числом MOD).

Мне интересно, есть ли еще алгоритм O(logn) для расчета

(a+sqrt(b))^n + (a-sqrt(b))^n (mod MOD)

Иррациональная часть sqrt(b) выглядит непростой при экспоненциальном вычислении. Все, что я могу сделать, это рассчитать части a+sqrt(b) и a-sqrt(b) по отдельности и сложить их вместе, а затем выполнить модульное, но если n огромен, его легко переполнить. Любые идеи?


algorithm math exponentiation exponent
person ChuNan    schedule 15.06.2014    source источник
comment
Алгоритм быстрого возведения в степень предполагает, что показатель степени является целым числом. В основе может быть что угодно. Это помогает?   -  person templatetypedef    schedule 16.06.2014
comment
@templatetypedef Спасибо, шаблон. Поскольку n очень велико, мне нужно выполнять модульную операцию каждый шаг, что мне кажется не таким уж простым, если база содержит иррациональные числа. Спасибо   -  person ChuNan    schedule 16.06.2014

Ответы (2)


arrow_upward
1
arrow_downward

Вы можете сделать это, вычислив (в ZM[x] / x²-b)

(a+x)^n+(a-x)^n mod (M, x^2-b)

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

В качестве альтернативы эти степенные комбинации являются решением линейной рекурсии 2-го порядка.

u[n+2]-2*a*u[n+1]+(a^2-b)*u[n]

куда

u[0]=2 and u[1]=2*a

так что вы можете использовать быстрое матричное возведение в степень системной матрицы этой рекурсии, снова получая алгоритм O (log (n)) (без учета битового размера).

Пример: согласно комментарию возьмите a=3, b=8, n=2 (и целые числа по модулю M=10^9+7, пример недостаточно велик, чтобы это имело значение)

В первом варианте вычислить u[n]=(a+x)^n mod (M, x^2-b), поэтому

u[0]=1
u[1]=3+x
u[2]=(3+x)^2 mod (x^2-8)=9+6x+8=17+6x

и удвоенный постоянный член равен 2*17=34

Во втором варианте рекурсия (с 2*a=6, a^2-b=1)

u[n+2]-6*u[n+1]+u[n]=0

так что первые элементы последовательности

u[0]=2
u[1]=6
u[2]=6*u[1]-u[0]=34
person Lutz Lehmann    schedule 15.06.2014
comment
Привет Lutzl, Спасибо за ваш вклад. Я попробовал несколько простых случаев, но результаты не согласуются с тем, что я вычислил напрямую: a = 3, b = 8, n = 2, x = 10^9+7, ответ должен быть 2*(3^2+ 8)=34... - person ChuNan; 16.06.2014
comment
Отлично работает в обоих вариантах, например, добавлены вычисления. - person Lutz Lehmann; 16.06.2014
comment
Идеальный! Я по ошибке установил x равным 10 ^ 9 + 7, теперь я знаю, что это просто переменная на протяжении всей итерации. Большое спасибо! - person ChuNan; 16.06.2014
comment
Ваш альтернативный подход (u(n) = pu(n-1)+qu(n-2)) кажется мне более простым, и да, здесь можно использовать быстрое матричное умножение. В то время как первый выглядит непростым для программирования из-за модульной работы с переменной частью x. - person ChuNan; 16.06.2014
comment
Первый так же прост, он похож на умножение комплексных чисел. (c0+c1*x)*(d0+d1*x)=(c0*d0+b*c1*d1)+(c0*d1+c1*d0)*x. - person Lutz Lehmann; 16.06.2014

arrow_upward
1
arrow_downward

Если вы расширите (a+sqrt(b))^n + (a-sqrt(b))^n, вы получите

  ( a + nC1 a^(n-1) √b + nC2 a^(n-2) b + nC3 a^(n-3) √b b + ... )
 +( a - nC1 a^(n-1) √b + nC2 a^(n-2) b - nC3 a^(n-3) √b b + ... )
= 2 a  +  0            + 2 nC2 a^(n-2) b  + 0 + ... + 2 nC4 a^(n-4) b^2 + ...

поэтому условия, включающие возможно иррациональные части, отменяются. (nC2 и т. д. — биномиальные коэффициенты).

RHS вышеприведенного можно довольно эффективно рассчитать с помощью целочисленной арифметики, поскольку вы можете связать каждый член последовательности с предыдущим. Однако есть n/2 членов, поэтому вычисление O (n).

Поскольку мы знаем, что результатом будет целое число, мы можем попробовать запустить алгоритм возведение в степень путем возведения в квадрат, отслеживая целых и дробных составляющих. Напишите a+sqrt(b) = x + y, где x — целое число, а y — дробная часть.

Находя квадрат этого мы имеем x^2 + 2 x y + y^2. Несмотря на то, что нас интересует только целая часть, у нас есть некоторые проблемы, так как есть целая часть 2 x y+ y^2. Это вызывает проблемы, так как для эффективного вычисления целой части мы будем знать много цифр y. Когда мы подошли к более высоким степеням, вам нужно больше цифр y, чтобы получить целую часть.

Я не думаю, что обычное умножение с плавающей запятой было бы достаточно для вычисления условий для очень больших n.

person Salix alba    schedule 16.06.2014