Zastanawiałem się nad zapisem liczby w różnych liczbowych systemach pozycyjnych.
Aktualnie jestem w stanie przejść prawie bez przeszkód pomiędzy dwoma systemami w ogólnej postaci:
a_n p^n + ...+ a_1p +a_0
Wykorzystuję schemat Hornera, zaczynając od cyfry najbardziej znaczącej.
W użyciu jest następujący algorytm rekurencyjny:
wyliczam różnicę między podstawami systemów r = p2-p1, może być liczbą dodatnią lub ujemną
na wejściu jest liczba (a_n ... a_0), wynik jest w postaci (b_m ... b_0), wartości pośrednie c_i można zapisać w dowolnym systemie, są to liczby całkowite
d = n, b_n = a_n; b_{n+1} = 0;
w pętli d = d-1;
(1) c_i = b_{i} + r * b_{i+1}
Ten krok 'psuje' cyfry, tzn. na miejscu cyfr pojawiają się liczby całkowite. Potrzebna jest 'naprawa', czyli przeniesienie nadmiarów lub wzięcie pożyczek: wykonuje się to w pętli po j>d-1:
b_j = c_j modulo podstawa,
b_{j+1} = b_{j+1} + c_j/ podstawa
Przy dużych podstawach liczby sa krótkie, pętle składają się z kilku prostych sum lub różnic.
Można pomyśleć o rozkładach liczb w taki sposób. Przekształcenia dla małych przyrostów są niesamowicie szybkie, można sprowadzić do 3*r sumowań lub odejmowań.
Konkretny przykład:
213 w systemie ósemkowym przekształcimy na system dziewiątkowy. Różnica r = 8-9 = -1
Pobieramy najbardziej znaczącą cyfrę:
2
Pobieramy kolejną cyfrę 1 oraz stosujemy przekształcenie (1)
2 1
2 1+2*(-1)
2 -1
wartość wymaga naprawy przez pożyczkę podstawy 9+(-1), uzyskujemy
1 8
dołączymy kolejną cyfrę 3
1 8 3
1 8+1*(-1) 3+8*(-1)
1 7 -5
Potrzebna jest pożyczka 9+(-5). Aktualna postać liczby to
1 6 4
Zatem 213 w ósemkowym to 164 w dziewiątkowym.
Bez dzielenia, same dodawania i odejmowania. Wszystkie wartości pośrednie są mniejsze niż pierwiastek z liczby.
