Mnożenie przez zmianę systemów, ulepszenie

Ćwicząc kolejne działania arytmetyczne wróciłem do algorytmu mnożenia przez zmianę systemów pozycyjnych. Opracowany algorytm wygląda w pseudokodzie następująco:
Dane: liczby a>=b.
Liczba a konwertowana do systemu o podstawie b, tu ma wygląd a'.
Mnożenie a' przez b wyglądające jak 10, iloczyn to liczba a'0.
Konwersja liczby a'0 na system początkowy, uzyskując a*b.
Wynik: iloczyn a*b. 

Tutaj cyfry są liczbami należącymi do przedziału [0,p), gdzie p jest podstawą systemu liczbowego.
Konwersja z systemu o podstawie r na system o podstawie b ma przebieg następujący, przy oznaczeniach:
a jest tablicą cyfr  [an ... a1 a0]
r=10^i jest potęga 10 spełniającą warunek r<= b < 10*r:

1. c =  najbardziej znacząca cyfra liczby a w systemie o podstawie r, c = [an]
2. Dopóki nie pobrane wszystkie cyfry liczby a powtarzaj 3.-5.
3. przenieś kolejną cyfrę z a do c: c = c + [ak] = [a'n ... ak]
4. dla wszystkich liczb tablicy c wykonaj  [cj] = [cj] - (b-r)*[c{j+1}], j>k-1
5. wszystkie liczby c sprowadź do cyfr za pomocą pożyczek lub przeniesień w systemie o podstawie b
6. a' = c
Liczba a' jest postacią liczby a w systemie o podstawie b

Niezmiennikiem konwersji jest fakt, że ciąg [an ... ak] przy podstawie pierwotnej p ma taką samą wartość jak ciąg [a'n ... a'k] przy podstawie p+(b-r).

Niezmiennik ten powoduje, że wszystkie operacje pętli 2.-5. z wyjątkiem ostatniej są operacjami do siebie odwrotnymi, i można je pominąć. Zostaje tylko jednorazowo przeprowadzona operacja 4. 5. dla liczby a'0.

Zatem mnożenie a*b w zależności od argumentów sprowadza się do kilku mnożeń na liczbach wielkości r<=b < a, których liczność jest wyznaczona przez a/b.

Pomnóżmy przykładowo 5.027.608.376 * 1008.
Wtedy b=1008, r=1000, i=3. Ciąg a to ciąg trójek cyfr dziesiętnych
[5, 27, 608, 376].
Z konwersji niesparowany jest przyrost o 8 ciągu z dopisanym zerem [5, 27, 608, 376, 0].
Krok 4. to dodawanie pomnożonych przez 8 wartości poprzedzających. Czyli mamy 4 mnożenia przez 8 i kilka dodawań. Uzyskujemy ciąg
[5, 67, 824, 5240, 3008].
Krok 5. to usunięcie nadmiarów, by wynik był w systemie o podstawie 1000:
[5, 67, 829, 243, 8].
Wreszcie ostatnia czynność, odczytanie wyniku iloczynu  w systemie dziesiątkowym:
5.067.829.243.008 


Mając liczby zawierające 480 oraz 500 bitów, możemy wziąć r = 2^i oraz system binarny. Ten sposób zamienia podany iloczyn na iloczyn liczb zawierających zaledwie około 480 bitów jedna (podstawa) oraz 500-480=20 bitów druga (cyfra 'dziesiątek' przy podstawie liczby 480-bitowej). Oznacza to, że zamieniamy  mnożenie dwu gigantycznych liczb na mnożenie przez małą wartość. Gdyż (b-r) jest liczbą mniejszą o co najmniej rząd wielkości od r.