Преобразование чисел

Выполнить преобразование 22₃ → Z₆. Последовательность действий и промежуточные результаты для наглядности представим в виде таблицы:

Как следует, 22₃ = 12₆.

Преобразование Z_p → Z₁₀ → Z_q

Разумеется, 1-ая и 2-ая часть преобразования не связаны вместе, что дает основание рассматривать их по отдельности.

Методы перевода 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 обозначение 2-ух операций: div — итог целочисленного деления 2-ух целых чисел и 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), из которых просматривается последующий метод перевода:

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

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