Sprawdzając możliwości systemu Fibonacciego zauważyłem możliwość zmniejszenia wartości dzielnej podczas dzielenia nie tylko na poszczególnych cyfrach, ale i na pozycjach.
Przykładowo dla liczby Fibonacciego
N = 101 010010 000100 101010 100100 010101F
chcemy znaleźć resztę z dzielenia przez 1087.
Dotychczas chciałem doprowadzić do liczby f zapisanej w systemie Fibonacciego, by na każdej pozycji była wartość 0 lub 2048 za wyjątkiem pozycji jedności, a następnie obliczyć f*(2048-1087)+f[0].
Ale można inaczej - wyznaczam wagi pozycji, sumując dwie wcześniejsze cyfry modulo dzielnik, tu 1087.
Uzyskam wtedy ciąg
... 485x 524 1048x 563 485x 78 407 758x 736 22 714 395 319x 76 243 920x 410 510x 987 610x 377 233x 144 89 55x 34 21 13 8x 5 3x 2 1x
koniec do 987 pokrywa się z liczbami Fibonacciego, dalej 987+610 = 1597 = 510 (1087). Zaznaczone x są pozycje ustawione w wartości Fibonacciego liczby N.
Suma oznaczonych pozycji jest równa 5435.
Liczba N jest podzielna przez 1087 gdy tak powstała liczba jest podzielna przez 1087, i mamy 5435 = 5*1087. Przekształcenie z N/1087 = 8219 zrobiło 5.
Kontynuując rekursywnie, jeśli dzielimy przez dzielnik bliższy liczbie, np. 5435 : 1087 uzyskamy wartość 2174.
Zatem mamy niezwykle mocne zmniejszenie wartości:
Liczba N zapisana w postaci Fibonacciego dzielona przez d sprowadza się do dzielenia przez N sumy liczb mniejszych niż d, których jest nie więcej niż połowa (+1 w najgorszym przypadku 101..0101) jedynek w liczbie N. Jest to bliskie 0,8 lg N ze złotego stosunku, czyli ewentualne rekursywne odwołania są tłumione wykładniczo.
Przekształcenie N do systemu Fibonacciego może być wykonane liniowo, współczynniki ciągu do sumowania też wyliczamy liniowo, korzystając podczas sumowania z ustawionych bitów liczby Fibonacciego N. Pozostaje jedno dzielenie, które wymaga znacznie mniej operacji niż pierwotne.
Szacuję na złożoność tego dzielenia pesymistycznie O(n lg n). Praktycznie szybsze ze względu na mniejsze wartości sumowane.
Brak komentarzy:
Prześlij komentarz