Ciąg fibonacciego

0

Jak obliczyć fib(n)^2 mod 1000000007?
Tu jest program który (wg. mnie) to wykonuje: https://ideone.com/cuGkK
Jednak wyniki nie są do końca poprawne.

PS. n<(2^31)-1

0

x.c=power_modulo_fast(x.c); a po co to? czemu nie
x.d * x.d % mod?

PARI/GP (polecam swoją drogą)
gp > lift(Mod([0,1;1,1],1000000007)^2423)

[70703389 976466852]
[976466852 47170234]

Twój program bez n+=2; oraz bez x.c=power.....
wejście:
2423
wyjście:
70703389 976466852 976466852 47170234

0

x.c=power_modulo_fast(x.c); a po co to? czemu nie
x.d * x.d % mod?

x.c x.c % mod - wydaje mi się, że przekroczy to zakresy. Obliczenia będą wykonywane po kolei, a więc najpierw wymnoży x.cx.c. Jeśli x.c np. będzie równe 976395637, to podniesienie tego do kwadratu zdaje się, że zostanie błędnie wykonane, nawet jeśli później jest %mod. Dlatego musiałem zastosować potęgowanie modularne.

Problem jest (tak mi się wydaje w tym), że funkcja matrix power(matrix x, int n) zwraca fib(n) % m. Natomiast ja następnie podnoszę to do kwadratu. A powinienem najpierw do kwadratu podnieść fib(n), a dopiero później zastosować %m.

Bo czy to jest prawdziwe? (aa) %m = ((a % m)(a % m)) % m.

Twój program bez n+=2; oraz bez x.c=power.....
wejście:
2423
wyjście:
70703389 976466852 976466852 47170234

n+=2 - muszę to zostawić (to jest mi potrzebne do rozwiązania zadania)
Nie wiem skąd pojawiły Ci się takie wyjścia.

Skróciłem nieco kod: http://ideone.com/pu2Hd

0

x.x jest typu long long, skoro mniejsze od 2^32-1 to można bezpiecznie podnosić do kwadratu

(aa) %m == ((a % m)(a % m)) % m (z definicji)
i korzystasz z tego w power_modulo_fast()

printf("%lld %lld %lld %lld\n", x.a, x.b, x.c, x.d)

0

x.x jest typu long long, skoro mniejsze od 2^32-1 to można bezpiecznie podnosić do kwadratu

Faktycznie, masz racje.

(aa) %m == ((a % m)(a % m)) % m (z definicji)
i korzystasz z tego w power_modulo_fast()

Sam się teraz zastanawiam dlaczego w to zwątpiłem i sobie przypominam..
Ponieważ (x.cx.c)%1000000007 oraz power_modulo_fast(x.c) zwracają różne wyniki... Nie do końca rozumiem dlaczego.
Np. n=200.
Wersja z użyciem (x.c
x.c)%1000000007, wynik:450435314
Wersja z użyciem power_modulo_fast(x.c), wynik: 41418325

0

gp > a=Mod([1,1;1,0],1000000007)^(200+2)

[Mod(407981060, 1000000007) Mod(878671356, 1000000007)]
[Mod(878671356, 1000000007) Mod(529309711, 1000000007)]

gp > a[1,2]^2
Mod(450435314, 1000000007)

zamiast
for (i=1; i<=b; i<<=1)
powinno być
for ( ; b ; b>>=1 )

a wiesz, że łatwo to przerobić tak by dobrze działało dla long long n, mod;

0

Więc jeśli dobrze zrozumiałem, to to już powinno być poprawne, tak?
http://ideone.com/1rfkB

0

gp > Mod(fibonacci(5+2),1000000007)^2
Mod(169, 1000000007)

0

gp > Mod(fibonacci(5+2),1000000007)^2
Mod(169, 1000000007)

Nie do końca rozumiem co chciałeś mi przez to przekazać.
(((fib(5+2) mod 1000000007)^2) mod 1000000007) = 169
OK, moj program tez tak zwraca..

0

i właśnie to chciałem pokazać

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0