Dzielenie z pomocą systemu Fibonacciego

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.

Konwersja do systemu Fibonacciego

W poście z 12 czerwca

Faktoryzacja oraz reszty z dzielenia w systemie Fibonacciego
wspomniałem o konieczności zamieniania liczby dowolnego systemu na system Fibonacciego. Ale pokazałem też przebieg który zwiększa cyfry, wstawiając na odpowiednich pozycjach potęgi 2. Ten schemat można odwrócić!

Dołączmy jeszcze jeden schemat do podanych w tamtym poście:
[0 0 2 0 0] = [0 1 0 0 1];
[0 0 3 0 0] = [1 0 0 0 1];
[0 0 4 0 0] = [1 0 1 0 1];
pominę przypadki brzegowe.
Teraz algorytm rekursywny w bardzo szybkiej pętli zmniejsza N aż 4 razy. Wewnątrz ma wolniejszy przebieg, gdyż wykorzystując schematy 'naprawia' liczbę do postaci Fibonacciego. 
Oto ten przebieg, wykorzystujący postać N w systemie czwórkowym:
IN N_4
i = 2^k, 2^k < N < 2^(k+2), czyli i<N<4i;
F_0+R = F_0+N%i, liczba Fibonacciego F_0 z resztą R (reszta zawiera cyfry N poza najbardziej znaczącą, te najbardziej znaczące dodajemy do postaci F_i)
powtarzaj dopóki i>1
  i /= 4;
  F_i = 4*F_i +HIGH(R); // dodajemy najbardziej znaczącą cyfrę R
  napraw F_i do systemu Fibonacciego;
OUT liczba w systemie Fibonacciego

Pomijając przekształcenia naprawiające liczbę, jest tu bardzo szybkie zchodzenie.
Przykład: N = 8934053d = 202011022211_4
Mamy N = 2^23 + 2011022211_4 = 2*2^22 + 545445, i = 2^22
F_0 = 10F z resztą 545445
i/=4, czyli naprawiamy liczbę [4 0+0]F = 10000F
następna iteracji zaczyna się od 40002 i kończy na
100 00000F z resztą 11022211_4 = 21157
Teraz jeden schemat działający na 400 00000 dostarcza
10101 00000F z tą samą resztą.
Kolejna naprawa 40404 00001 przekształca się do
101 00010 00100F z resztą 1022211_4 = 4773
I dalej:
1 00101  01000 10000F z resztą 22211_4 = 677
1001 00010 10100 01001F z tą samą resztą
10 00101 00100 01010 10010F z resztą 2211_4=165
10001 00000 00100 10010 00100F z resztą 211_4=37
100 00010 10100 00010 10100 10001F z resztą 11_4 = 5
1 00000 00100 01001 00100 10000 10000F z resztą 1_4 = 1
i ostatnie, gdyż mamy już i=2^2=4
101 01001 00001 00101 01010 01000 10101F, co jest wartością Fibonacciego liczby N.