Пример 4.1

Очевидно, первая и вторая часть преобразования не связаны друг с другом, что дает основание рассматривать их по отдельности.

Алгоритмы перевода Z₁₀ → Z_q вытекают из следующих соображений. Многочлен (4.1) для Z_q может быть представлен в виде:

* Такое представление называется схемой Горнера.

где т - число разрядов в записи Z_q, а b_j (j = 0...m - 1) - цифры числа Z_q.

Разделим число Z_q на две части по разряду номер i; число, включающее т - i разрядов с т - 1 -го по i-й обозначим γ_i, а число с i разрядами с i - 1-го по 0 -й - δ_i. Очевидно, i [0, т - 1], γ₀ = δ_m-1 = Z_q. Позаимствуем из языка PASCAL обозначение двух операций: div - результат целочисленного деления двух целых чисел и mod - остаток от целочисленного деления (13 div 4 = 3; 13 mod 4 = 1). Теперь если принять γ_m-1 = b_m.₁, то в (4.2) усматривается следующее рекуррентное соотношение: γ_i = γ_i+1 ∙ q + b_i, из которого, в свою очередь, получаются выражения:

Аналогично, если принять δ₀ = b₀, то для правой части числа будет справедливо другое рекуррентное соотношение: δ_i = δ_i-1 + b_i ∙qⁱ, из которого следуют:

Из соотношении (4.3) и (4.4) непосредственно вытекают два способа перевода целых чисел из 10-ной системы счисления в систему с произвольным основанием q.

Способ 1 является следствием соотношений (4.3), из которых просматривается следующий алгоритм перевода:

1) целочисленно разделить исходное число (Z₁₀) на основание новой системы счисления (q) и найти остаток от деления - это будет цифра 0-го разряда числа Z_q;

2) частное от деления снова целочисленно разделить на q с выделением остатка; процедуру продолжать до тех пор, пока частное от деления не окажется меньше q;

3) образовавшиеся остатки от деления, поставленные в порядке, обратном порядку их получения, и представляют Z_q.

Блок-схема алгоритма представлена на рис.4.1. Обычно его представляют в виде «лестницы».