On 14.05.2016 11:10, Roman W wrote:
> On Fri, 13 May 2016 17:52:46 +0200, Borneq <b...@a...hidden.pl>
> wrote:
>> W dniu 13.05.2016 o 17:46, Borneq pisze:
>> > Co to są liczby Fibonacciego - wiadomo, ale co to są liczby
> Fibonacciego
>> > któregoś rzędu?
>> Już wiem, normalne inicjowane są dwiema jedynkami , inne większą
>> liczbą

Pomijasz najistotniejsze. Element ciągu jest sumą nie dwóch,
ale k poprzednich elementów.
Niby oczywiste, ale można przeoczyć.

>> jedynek, i tak dla trzech:
>> 1+1+1=3 1+1+3=5 1+3+5=9
>> co nam daje 1 1 1 3 5 9 17 31 57
>
> Czy istnieje rozwiązanie analityczne dla rzędu N > 4?

Rozwiązanie liniowej rekurencji sprowadza się do znalezienia
pierwiastków wielomianu. To dla n>4 bywa upierdliwe;-)


Wiemy, że rozwiązaniami podstawowymi są ciagi geometryczne.
q^k

(rozwiążaniem jest kombinacja liniowa takich rozwiązań podstawowych
spałniająca warunki początkowe)

które spełniają rekurencję:

a[n]+a[n+1]+..a[k-1] = a[k]

czyli
1 + q + q^2.. + q^(k-1) = q^k

q^k - q^(k-1) - q^2 - q - 1 = 0 (1)


(q^k-1)/(q-1) = q^k

q^k -1 = q^(k+1) - q^k

0 = q^(k+1) - 2 q^k + 1

Dla k=2

(q^2-q-1)

pierwiastkami są fi i bar{fi}

Zgadza się.


Do rzeczy... wielomian (1) wygląda ładnie, ale
pierwiasków oczywistych nie widać. Mathematica ich też nie widzi
dla k>4:(

Do ataku nemerycznego można użyć równoważnego

-(q^k-1)/(q-1) + q^k

lub ładniejszego ale z dodatkowym sztucznym pierwiastkiem równym 1

q^(k+1) - 2 q^k + 1

Patrząc na te wykresy widać, że pierwiastki są
jeden w okolicy liczby 2
k-1 w okolicach (zespolonych) pierwiastków z jedynki (z pominięciem
samej jedynki).



To daje nam jakościowe oszacowanie, jak szybko ten ciąg rośnie,
ale pewnie chceilibyśmy go policzyć.
Dokładnie policzyć element nr 3535436743678357 ;-) Modulo
10^18 niech dla ulatwienia bedzie.
Jechanie rekurencją odpada, a wspołczynniki wzoru 'analitycznego'
znamy być możę nie dostatecznie dokładnie, aby wyzanczyć liczbę
jednosci.

Tu przydatna jest pewna sztuczka, używana już przy Fibonaccim.

Weźmy macierz
A =
[1 1 1 1 1 1 1 1]
[0 1 0 0 0 0 0 0]
[0 0 1 0 0 0 0 0]
[0 0 0 1 0 0 0 0]
[0 0 0 0 1 0 0 0]
[0 0 0 0 0 1 0 0]
[0 0 0 0 0 0 1 0]

Opisuje ona iterację stanu z naszego ciągu. Jeśli wsadzimy w nią wektor
an, an-1... dostaniemy wektor an+1,an...

Jeśli zaczniemy od wektora jednostkowego v=[1;1;1;1;1;1;1]

Pierwszym elementem wektora (A^n)v
będzie n+k ty element ciągu Fib.

A^n obliczami potęgowaniem binarnym, log(n) mnożęj, każde
po k^3 dzialań, łączny koszt O(log(n) k^3)


pzdr
bartekltg