[Algorytmy] Ciąg fibbonaciego sposoby obliczania.

[pi0tras]

Cześć wam, cieszę się, że na tym forum jest specjalny dział dotyczący programowania.

Otóż mam za zadanie napisania kawałka kodu który oblicza elementy ciag fibbonaciego, ale to nie wszystko. Musi to być niezwykle wydajna metoda szybsza niż metoda liniowa - musi być ona polilogarytmiczna. Jakie znacie sposoby algorytmiczne obliczania ciągu fibbonaciego ?? Na pewno odpada metoda rekurencyjna która jest wykładnicza.

[Spektralny]

Co gdyby rozważać części całkowite zaokrągleń potęg ze wzoru Bineta?

Kod: Zaznacz cały

https://pl.wikipedia.org/wiki/Ci%C4%85g

... B3r_Bineta

[pi0tras]

Hm myślę, że raczej lepsze by było zaokrąglenie funkcją round() (która zaokrągla do najbliższej liczby), a ogólnie to byłby wtedy czas stały (gdyby uznać, ze potęgowanie wykonuje się w czasie stałym) a nie polilogarytmiczny, myślałem już o tym. Właściwie to nie ma nawet gwarancji że obliczone wartości byłby poprawne po tych zaokrągleniach do najbliższej całości. Gdyby napisać procedurę funkcyjną która wykonuję potęgowanie w czasie polilogarytmicznym to myślę, że problem byłby w jakimś stopniu rozwiazany, potem gdyby wziąć pod uwagę błędy zaokrągleń typów zmiennoprzecinkowych i udowodnić, że nie przekraczały by jedności to udałoby się wtedy .

-- 16 lis 2015, o 19:05 --

ooo mam tutaj taki link:

Kod: Zaznacz cały

http://www.algorytm.edu.pl/algorytmy-maturalne/potegowanie-szybkie.html

Jeśli uda mi się udowodnić, że błędy obliczeniowe na zmiennych typu float/double nie przekraczają \(\displaystyle{ 0.5}\) to wtedy uda mi się to zrobić . Niestety błędy większe niż \(\displaystyle{ 0.5}\) będą powodowały otrzymywanie błędnych wyników. Bo funkcja round działa w ten sposób, że dodaje \(\displaystyle{ 0.5}\) do wartosci liczbowej a potem zwraca liczbę całkowitą z tej wartości.

[Afish]

Zazwyczaj liczy się to potęgując macierze.

[pi0tras]

Hm nic to nie da, im większa potęga tym większy błąd będzie który przekroczy 0.5 w którymś momencie w dodatku ta metoda mnożenia w czasie polilogarytmicznym jest dostosowana do liczb naturalnych. Co masz na myśli z tym potęgowaniem macierzy ? Z tego co wiem no mnożenie macierzy jest rzędu \(\displaystyle{ n^{3}}\), ale w sumie o potegowaniu nie wiem nic.-- 16 lis 2015, o 19:55 --A widzę ! Dzięki Ci bardzo za ten pomysł !