Pomysły ze zmianami systemów liczbowych skutkują, że dzielenie staje się łatwiejsze i szybsze niż niektóre algorytmy mnożenia. Wystarczy, by w ilorazie
iloraz = dzielna / dzielnik
zapisać dzielną w systemie o podstawie dzielnik. Cyfra najmniej znacząca to reszta z dzielenia, pozostałe to wartość ilorazu. Wystarczy tylko jeszcze przekonwertować.
Technika ta wspomaga także szukanie największego wspólnego dzielnika. Przy czym do znajdowania złożoności lgorytmu wygodniejszy jest system binarny.
Podzielmy dzielną na paczki długości o jeden mniejszej niż długość dzielnika, jest ich a = sufit (dzielna/ dzielnik). Tak przygotowana dzielna jest liczbą a-cyfrową w systemie o podstawie b=2^i, gdzie
2^i <= dzielnik < 2^{i+1}
Przechodząc po cyfrach binarnych dzielnika, jeśli na danej pozycji 2^j występuje 1, konwertujemy do systemu o podstawie b = b+2^j. Złożoność tego algorytmu jest kwadratowa ze względu na liczność cyfr równą a. Korzysta z odejmowania złożoności liniowej względem cyfr. W najgorszym przypadku mamy 1 na wszystkich p pozycjach dzielnika. Powtarzamy p razy.
Uzyskamy część całkowitą i resztę.
Jeżeli reszta jest równa 1, nwd jest równe 1, kiedy zaś reszta jest równa 0, znaleźliśmy nwd równe aktualnej podstawie systemu.
W innych przypadkach powtarzamy postępowanie dla dzielnika i reszty. Uzyskujemy ciąg wartości zmniejszających się co najmniej dwukrotnie. Zatem jest ich co najwyżej tyle to cyfr dzielnika p.
Podsumowując, złożoność liczb n<m
nwd ( n, m ) = O( n(ap)^2 ) = O( n(m/n log n)^2 )
dla dużych n nie przekracza złożoności kwadratowej O(m^2), którą się przyjmuje klasycznie, gdyż najlepsze algorytmy działają nieco szybciej.
Przykład,
nwd( 1517, 1073 )
zapisujemy 1517 = 101 1110 1101_2 w systemie o podstawie 1073 = 100 0011 0001_2
1517 = 1 . (1 1110 1101)_{1024} = 1 493_{1024}
konwersja łącznie o przyrost 11 0001_2 = 49, generuje liczbę 1 . 444_{1073}
powtarzamy dla 1073 oraz 444 = 1 1011 1100_2
1073 = 4 49_{256} = 2 305_{384} = 2 185_{444}
powtarzamy dla 444 oraz 185 = 1011 1001_2
444 = 3 60_{128} = 2 74_{185}
powtarzamy dla 185 oraz 74 = 100 1010_2
185 = 2 57_{64} = 2 37_{74}
powtarzamy dla 74 oraz 37 = 10 0101_2
74 = 2 10_{32} = 2 0_{37}
ostatnia cyfra 0, zatem dzielnikiem jest aktualna podstawa 37
nwd( 1517, 1073 ) = 37
