Dzielenie przez przedstawienie w innym systemie

Kończę dopieszczanie algorytmu dzielenia przez przedstawienie w innym systemie. Uzyskujemy resztę, a jak zastosujemy jeszcze raz przekształcenia od końca, także iloraz.

Zasada jest następująca:
mamy podzielić liczby a/b , a<b;
znajdujemy długość binarną liczby b:  2^k <= b < 2^{k+1};
dzielimy a na paczki mające dokładnie k bitów począwszy od cyfr najmniej znaczących, jest to przedstawienie a w systemie o podstawie 2^k;
stosujemy algorytm konwersji na system o podstawie b, przyrost  r = b-2^k ; algorytm ten jest podany w innym poście. Polega na tym, że dla kolejnych ciągów cyfr najbardziej znaczących stosujemy przekształcenie nie zmieniające wartości liczby a*(b-r) + c= a*p + (c+ar), oraz 'naprawiamy' za pomocą pożyczek lub nadmiarów tak, aby liczba na każdej pozycji stała się cyfrą;
cyfrą najmniej znaczącą jest reszta, odcinamy ją;
aby uzyskać iloraz, stosujemy algorytm konwersji na system o podstawie 2^k, przyrost r = -(b-2^k) ;
sklejamy paczki k-bitowe a w jedną wartość, będącą  ilorazem.

Mnożenie możemy przygotować w podobny sposób, bliższe informacje w następnym poście: "Mnożenie przez zmianę systemów"
Zatem ten sposób dzielenia jest łatwiejszy i mniej pracochłonny niż mnożenie.

Zachowanie algorytmu.
Gdy liczba a >> b, mamy dużo cyfr, oraz algorytm konwersji jest kwadratowy ze względu na krotność paczek mających k bitów. Dla dużych liczb stosunek ten się zmniejsza, co prowadzi do 'zmniejszania się' liczności cyfr , to z kolei bardzo upraszcza i przyspiesza konwersję. Jest to mile widziane dla bardzo dużych liczb.
Przyrost jest liczbą nie przekraczającą 2^k. Przypadkiem najgorszym są liczby nieco poniżej 2^k-1, dla nich przyrost jest największy.

Algorytm konwersji można zmodyfikować stosując iteracyjnie przyrost 2^m dla ustawionego bitu b[m], oraz malejących m= k ..  0.


Przykład: dzielimy liczby (zapis szesnastkowy dla zwiększenia czytelności)
-->

0x9927E4 : 0x7C  ( 10 037 137 : 124) 
liczba 0x7C = 111 1100b ma długość 7, podstawą jest 2^6 = 64 
liczbę 0x9927E4 = 1001 1001 0010 0111 1110 0100b dzielimy na paczki oddzielane kropkami

1001 10.01 0010 . 0111 11.10 0100 : 1.11 1100 = 38 18 31 36_{_{64}} : 1 60_{_{64}
gdyż 100110b = 38, 010010 = 18 itd. 
liczbę tę konwertujemy na system większy o 60, czyli iteracyjnie będziemy 'naprawiać' w systemie  o podstawie 124 wyrażenia: 38*64 +18 = 38*124 + (18-60*38) =  38*124 + (-2262) = 19*124+}94, i tak dalej ((19*124)+94)*64+31 = (19*124 + (94-60*19))*124 + (31-60*94) = ... 

liczba po konwersji : 5 32 97 40_{_{124}} , reszta 40
mamy iloraz zapisany w systemie o podstawie 124: 5 32 97_{124}, należy go przerzucić do systemu o podstawie 64. Konwersja zaczyna się od 5*124 + 32 = 5*64 + (32+60*5) = ... 

liczba po konwersji : 19 48 49_{_{64}} = 0x13C31 (80 945) 
tu znowu rozpisujemy 19 = 010011, 48 = 110000, 49 = 110001, sklejamy i odczytujemy binarnie.  

Podsumowanie dzielenia:  10 037 137 : 124 = 80 945 r. 40