Golden Ratio Чтобы найти числа Фибоначчи

Question

Я должен найти Xth Фибоначчи Номер F(X)%1000000007
т.е. Для примера Если я должен плавник d X(350) = 672262724. Вот Code

Теперь я заинтересован в поиске с помощью Golden Ratio A=1.61 B=-0.61

X(350) = (A^350-B^350+1)/Math.sqrt(5) 

Но как заботиться о Modulo, как это дает мне неправильный ответ, если я просто использовать % операцию

Вот мой Код:

public static double super_pow(double A , long B){ 

     double o=1; 

     while(B>0){ 

      if((B&1)!=0) o*=A; 

      A*=A; 
      B/=2; 
      o%=mod; 
      A%=mod; 
     } 



     return (o+1)%mod; 
} 

Я прекрасно работает, когда ответ less thanMod. Но для большой ценности он дает неправильный ответ.

Answer 1

Это не работает. Вы не можете притворяться, что работаете в конечном поле, а затем делите на иррациональное число, или, скорее, можете, но это не имеет смысла. Вы просто получите некоторые нерелевантные иррациональные результаты, которые не имеют никакого отношения к ответу, который вы хотели. Вам нужно будет все это сделать в R, если вы пойдете туда. Для этого требуется вычислить чрезвычайно большие числа, а затем взять остаток, числа с плавающей запятой в какой-то момент превзойдут точность и дадут вам вздор. Бит с весом 1 всегда важен, если вы собираетесь взять остаток, как это, но он не обязательно присутствует в числе с плавающей запятой, в зависимости от экспоненты. Но, возможно, вы это знали, и именно поэтому вы решили не делать этого.

Вы также не можете сделать это с помощью математики конечного поля в этом случае. Iff 5 - квадратичный вычет в поле, в котором вы работаете, эта конструкция все еще работает. A и B не будут phi и phibar, но (sqrt (5) +1)/2 и (1-sqrt (5))/2 соответственно, которые в конечной математике поля будут работать на «смешные номера», которые выглядят полностью не связанные с phi и phibar (но на самом деле являются их конечным полевым аналогом). И, конечно, если вы сделаете это, в вашем коде не будет Math.sqrt. Вам нужно число x такое, что x * x = 5по модулю что-то, а не диадическое рациональное приближение решения среди реалов.

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

следующие работы по модулю 1009: 856 * (627 ^п - 383 ^п)

Другие алгоритмы все еще работают, такие как повышение определенную матрицу 2х2 на п-й степени, и его слегка оптимизированную версию (избегая избыточных вычислений).