Mi się zgadza

Potwierdzam. Wiem że późno, ale próbuję właśnie wygenerować jakoś więcej testów. Mogą być bardzo niepoprawne :P Ktoś coś?

https://drive.google.com/file/d/16886XWmMHhMosMOn3iOdsgctrcsfsFFX/view?usp=sharing

Potwierdzam wszystko wyżej.

Potwierdzam wszystko

Można szybciej zamieniać na system binarny. W publikacji "On the Complexity of Fibonacci Coding" jest opisany algorytm działający w czasie O(M(n) lg n) zamiany na system binarny i w drugą stronę, gdzie M(n) to czas mnożenia liczb w zapisie binarnym.

Potwierdzam :)

Potwierdzam :)

https://drive.google.com/open?id=1o-qSFn3UNC70JBLgnpLBn9cQYK3qSctw
Pierwszy test to maxtest

Potwierdzam wszystko

4 testy z (prawie) maksymalnym n i m. a,b <= 3000. Niekoniecznie świetne testy, ale przynajmniej planarne XD Ktoś potwierdzi, ktoś zaprzeczy?
https://drive.google.com/drive/folders/1IvE5hN5VYaLgSC8mFmv7-kRrCIvtowW_?usp=sharing

Również potwierdzam wszystko

Potwierdzam wszystko

Potwierdzam wszystkie testy.

obstawiam 15.

1. Modyfikuję reprezentację Fibonacciego (Zeckendorfa) tak żeby jedyne niezerowe współczynniki były na pozycjach F0, F1, F40, F41, F80, F81, itd.
2. Teraz obliczam binarnie te liczby Fibonacciego i dodaję odpowiednie wielokrotności.
3. Mnożę binarnie (najprostszym algorytmem).
4. Dzielę przez ..., F120, F80, F40, F0, otrzymując reprezentację w której niezerowe współczynniki są na pozycjach F0, F40, F80, F120, ...
5. Naprawiam reprezentację tak żeby były same jedynki oddzielone zerami, robiąc to samo co w niebieskiej książeczce po dodawaniu ale na wielokrotnościach potęg dwójki, zaczynając od najwiekszej.

Krok 1 jest w czasie O(n), kroki 2,3,4 w czasie O(n^2/w^2) (gdzie w=32 to liczba bitów w słowach komputera), a krok 5 w czasie O(nw). Razem O(n^2/w^2) (o ile n > w^3). Zauważmy że to jest o(n^2), bo log n < w (skoro n da się reprezentować w zmiennej), więc O(n^2/w^2) = O(n^2 / log^2 n).