08 września 2017

Kolejne kandydatki na wielomianowe argorytmy faktoryzacji

Rachowanie w systemie, w którym jest dużo cyfr jest tak skomplikowane, że oprócz tabliczki mnożenia należy wprowadzać także tabliczkę dodawania. Nie zawsze przewidzimy dokładnie postaci wyniku.
Zatem należy zmienić definicję działania. Dodawanie jest następujące dla naturalnych a,b:
a+0 = a,
a+b = max(a,b) + min(a,b);
a+b = (inc a) + (dec b);
Działania maksimum max, minimum min, incrementacji inc (zwiekszanie o jeden) i dekrementacji dec są klasyczne.
Odejmowanie można przedstawić rekursją:
a-0 = a,
a-b = (dec a) - (dec b). 

Mnożenie też jest zdefiniowane dla uporządkowanych malejąco wartości a, b:
a*0 = 0,
a*1 = a,
a*b = (inc a)*(dec b) + (a-b) + 1
Wynika to  faktu (a+1)(b-1) = ab-a+b-1.
Można odwrócić kierunek, a wtedy (inc a)*(dec b) = a*b-(a-b)-1.

Stosując przedstawione działanie do systemu dziesiętnego, oraz dołączając do  większej wartości nadmiar z reszty, uzyskamy np. dla  liczby 51:
51 =
25*2 +1 =
24*2 +3 =
23*2 +5 =
22*2 +7 =
21*2 +9 =
20*2 +11 =
19*2 +13 =
18*2 +15 =    oraz (17*3)-(17-3)-1= 17*3-15
17*3 = 
16*3 +3 =
15*3 +6 =
14*3 +9 =
13*3 +12 =
12*4 +3 =
11*4 +7 =
10*5 +1 =
9*5 +6 =
8*6 +3 =   
7*7 +2      

Widać, że dla większych wartości przechodzenie wymaga operacji liniowych lub stałych, reszty układają się we wzory, które można ominąć rozwiązując liniowe równanie aproksymacyjne zmiennej k, w którym pominiemy resztę
a-k = bk,
stąd k = a/(b+1). Tyle wyrażeń można pominąć, np. dla 25*2+1 pominiemy 25/3=8, a wtedy 25-8=17, b wzrośnie o 1, zaś c wzrastając o bk przybliży a.
Dla 9*5+6 mamy przeliczenie: 10*4+(9-5)+1+6 = 10*4+5+6, zaś ponieważ 5+6>10, zwiększamy a o jeszcze jeden.

Dochodzimy do algorytmów:
niech a = b = sqrt N.
inicjalizacja a*b+c = N
dopóki c<>0 lub 1<b powtarzaj
  c= c+(a-b)+1; inc a; dec b; if(c>a) {c-=a; inc a;}
return dzielniki a,b;

Drugi, zmieniający kierunek przebiegu  przebiega mniej więcej tak:
inicjalizacja a=floor{N/2}; b=2; c=N-a*b;
dopóki c<>0 lub a<b powtarzaj
  inc b; k=floor(a/b); a-=k-1; c=c+a-k*b;

Dla większych ilorazów a/b nie warto liczyć k, lecz wykorzystać bezpośrednio przekształcenie z definicji i porównać c z a, modyfikując je przy przenoszeniu.
Tłumienie wartości k jest wzmacniane, iloraz czynników a/b dąży do 1.

Algorytmy dla małych wartości są zbyt skomplikowane do użycia. Ale dla dużych liczb? Znów proste i szybkie działania stałe lub liniowe.