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.
[Algorytmy] Ciąg fibbonaciego sposoby obliczania.
- Spektralny
- Użytkownik
- Posty: 3976
- Rejestracja: 17 cze 2011, o 21:04
- Płeć: Mężczyzna
- Lokalizacja: Praga, Katowice, Kraków
- Podziękował: 9 razy
- Pomógł: 929 razy
[Algorytmy] Ciąg fibbonaciego sposoby obliczania.
Co gdyby rozważać części całkowite zaokrągleń potęg ze wzoru Bineta?
... B3r_Bineta
Kod: Zaznacz cały
https://pl.wikipedia.org/wiki/Ci%C4%85g
- pi0tras
- Użytkownik
- Posty: 283
- Rejestracja: 7 lut 2011, o 16:41
- Płeć: Mężczyzna
- Podziękował: 91 razy
- Pomógł: 1 raz
[Algorytmy] Ciąg fibbonaciego sposoby obliczania.
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:
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.
-- 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.
- pi0tras
- Użytkownik
- Posty: 283
- Rejestracja: 7 lut 2011, o 16:41
- Płeć: Mężczyzna
- Podziękował: 91 razy
- Pomógł: 1 raz
[Algorytmy] Ciąg fibbonaciego sposoby obliczania.
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ł !