Notacja Zeckendorfa używana przy liczbach Fibonacciego zasugerowała mi próbę wykorzystywania przesunięć reszt przy działaniach typu 19+3 = 12 + przesunięcie 10.
Kilka prób i powstał algorytm, w którym znów nie dzielimy, przynajmniej nie operatorem dzielenia. Dzielenie jednak występuje, lecz jest zaszyte bardzo specyficznie.
Jakie liczby najłatwiej nam dzielić? Takie, w których na miejscu cyfr występują tylko zera i dzielnik. Np.
7077707707070707070777770700007
jest podzielna przez 7, zaś wartość ilorazu to ta sama liczba, w której zastępujemy siódemki jedynkami.
W praktyce nie jest tak dobrze. występuje reszta. Resztę tę można przesuwać, i klasycznie przesuwa się ją do cyfry najmniej znaczącej. Cyfra ta rozrasta się, aż nadmiar należy wrócić do liczby rozkładanej. Można w tym celu posłużyć się dodatkową cyfrą binarną A, której ustawione bity sygnalizują daną wartość liczbową d.
Wtedy podczas algorytmu wykorzystamy równość:
d*A = (d+2)*A - 2A
odejmując podwojony bit A od reszty przechodząc z wartości d na (d+2).
Kiedy przystąpiłem do implementacji tego algorytmu, oceniłem, że lepiej będzie zmienić kolejność przesunięć do cyfry najbardziej znaczącej R.
I algorytm zmienił swoje możliwości, uprościł się likwidując cyfrę binarną A.
Algorytm teraz działa następująco:
liczbę N = n_m 2^m + ... + n_1*2 + n_0
zapisujemy w tablicy binarnej b bez najbardziej znaczącego bitu r=n_m. Dalej przekształcenia można zapisać:
for( d=3; d< sqrt N; d=d+2) {
v=0;
for( i=0; i<m; i++) {
if( b[i] ) v= v+(d-2);
if( 2|d ) b[i]=0; else { v = v-d; b[i]=1; }
v = v/2;
}
r = r+v;
while( r<0 ) { r= 2*r+b[m]*d; m--; }
if( r>d-1 ) {
if( ~(2|r) ) { b[m]=1; r=r-d; } else b[m]=0;
m++;
r = r/2;
}
if( 0==r ) return dzielniki d, A(binarnie)
if( 2*m< log N ) return liczba pierwsza
}
Algorytm sprawdza stałą krotność liczb na minutę (prawie, ma lekką tendecję przyspieszania, gdyż zakres [0..m] nieco drga zmniejszając m).
Ma złożoność arytmetyczną O(n log n). Cechuje się tłumieniem rozwoju reszt.
I jak na razie, jest bardzo szybki jak na dotychczasowe rozważania.
Przesunięcia nie powiedziały jeszcze ostatniego słowa. Podejrzewam, że wkrótce odsłonią mi coś nowego.
