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.