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.
Brak komentarzy:
Prześlij komentarz