Перевод чисел между системами счисления 1

Модулярная арифметика имеет ряд преимуществ по сравнению с позиционной. Они заключаются и в скорости работы, параллелизме, требованиям к разрядности чисел. Однако реализовать всю систему целиком исключительно на основе непозиционной арифметики не всегда является целесообразным и возможным. Например, когда происходят определенные расчеты, то результат в большинстве случаев должен быть представлен позиционно, иначе в нем может просто не быть смысла. Кроме того, крайне часто модулярная арифметика используется совместно с традиционной, дополняя и совершенствуя ее. В таких системах быстрое выполнение перевода чисел в обе стороны жизненно важно.

Прямой перевод в систему остаточных классов

Как я отмечал ранее, система остаточных классов (СОК) есть непозиционная система счисления, числа в которой представлены в виде наборов остатков от деления на заранее подобранные основания (которые являются взаимно простыми между собой числами). Казалось бы в определении данной системы четко прописан алгоритм перевода в нее: взять остатки от деления исходного позиционного числа на числа, выбранные в качестве оснований, и записать их по порядку. Тем более большинство языков программирования и проектирования вычислительных систем данную операцию поддерживают вполне неплохо. Задача усложняется, когда в качестве позиционного числа принимаются числа большой разрядности, представленные в так называемой "длинной" арифметике. Данная форма записи числа применяется при ограниченности разрядной сетки аппаратуры, используемой для вычислений. Если разрядная сетка ограничена, допустим, k битами, то длинное число представляется в системе счисления с основанием 2^k и последовательно записывается в память (например, в виде массива). Задача получения остатка от деления становится в таком случае нетривиальной. Методы ее решения можно найти в [1-3]. В нашем случае небольшое упрощение достигается за счет того, что остаток ищется от деления "большого" числа на "маленькое", одноразрядное с точки зрения выбранной системы счисления. Потому можно операцию вычисления остатка от деления упростить путем сведения к малоразрядным числам, что позволит уйти от необходимости реализации операции деления. Рассмотрим один из приемов вычисления остатка от деления на малоразрядное число. Пусть, допустим, вычислительная платформа, на которой мы работаем, может обрабатывать k-разрядные числа. Пусть нам необходимо вычислять остатки от деления чисел, представленных в виде:

A=a_0\cdot{2^0}+a_1\cdot{2^k}+a_2\cdot{2^{2k}}+...+a_i\cdot{2^{i\cdot{k}}}+...+a_m\cdot{2^{m\cdot{k}}}

С другой стороны число A можно записать в виде массива:

A=\left [a_m,a_{m-1},...,a_2,a_1,a_0 \right ]

где каждое из чисел a_i имеет разрядность k и является разрядом в выбранной системе счисления. Здесь специально разряды упорядочены от старшего к младшему, как это делается в традиционных системах счисления (десятичной, двоичной и т.д.), что демонстрирует общую природу классической и длинной арифметики. Предположим, что нам нужно найти остаток от деления произвольного числа A на некоторое фиксированное p разрядностью k. Основываясь на форме представления A, получить алгоритм вычисления достаточно просто. Возьмем остаток от деления A:

A\mod p=\left (\sum\limits_{i=0}^m{a_i\cdot{2^{i \cdot k}}} \right )\mod p = \sum\limits_{i=0}^m\left ({a_i\cdot{2^{i \cdot k}}}\mod p \right )

Разбираясь с отдельным элементом последней суммы, заметим, что числа w_i = 2^{i \cdot k} \mod p являются константами для i=0,1,2,...,m. Потому достаточно на каждом шаге суммирования вычислять один остаток, одно произведение и снова один остаток, что вполне можно делать и параллельно:

A \mod p = \left ( \sum\limits_{i=0}^m{\left ( (a_i \mod p) \cdot w_i \mod p \right )} \right ) \mod p

В итоге все сводится к достаточно легко реализуемым операциям. Подвохом в данном случае может стать необходимость перехода от разрядности k к разрядности 2 \cdot k при реализации умножения. Однако есть способы избежать данную неприятность, к которым можно отнести популярные алгоритмы Монтгомери и Карацубы. Стоит так же отметить, что операция сложения может привести к вычислениям с разрядностью k+1. В некоторых случаях может помочь выбор p специального вида. Таким образом можно составить алгоритм умножения для каждого из модулей системы оснований и искать остаток по нему независимо от остальных. Различие в вычислениях будет заключаться в заранее рассчитываемых значениях w_i, индивидуальных для каждого из модулей.

Перевод из системы остаточных классов: Китайская теорема об остатках

Обратный перевод - восстановление позиционного значения числа по остаткам - дело более хлопотное. Проблема заключается в том, что нам необходимо фактически решить систему сравнений с одним неизвестным и n уравнениями, что приводит к сложным и громоздким вычислениям. Основной задачей многих исследований в области СОК является оптимизация этого процесса, ведь он лежит в основе большого числа алгоритмов, в которых в том или ином виде необходимо знание о позиции чисел на числовой прямой. В теории чисел метод решения обозначенной системы сравнений известен уже очень давно и заключается в следствии основной теоремы модулярной арифметики: Китайской теоремы об остатках (КТО) [4]. Данная теорема дает возможность найти позиционное представление числа A=(a_1, a_2, ..., a_n) в системе взаимнопростых оснований {p_1, p_2, ..., p_n}, где a_i=A \mod p_i для i = 1,2,...,n и P=\prod \limits_{i=1}^n {p_i}, по следующей формуле:

A \mod P = \left ( \sum \limits_{i=1}^n a_i \cdot \left | \left ( \frac{P}{p_i} \right )^{-1} \right |_{p_i} \cdot \frac{P}{p_i} \right ) \mod P

В данной формуле число

B_i = \left | \left ( \frac{P}{p_i} \right )^{-1} \right |_{p_i} \cdot \frac{P}{p_i}

можно вычислить заранее. Данные числа в выбранной СОК называются ортогональными базисами и их остаточное представление имеет следующий вид: B_1 = (1,0,0,...,0), B_2 = (0,1,0,...,0), ..., B_n=(0,0,0,...,1). Здесь значение s = \left | \left ( t \right )^{-1} \right |_{p} означает мультипликативную инверсию по модулю p и требует выполнения условия: s \cdot t = 1 \mod p. С учетом введенных обозначений приведенная ранее формула перепишется следующим образом:

A \mod P = \left ( \sum \limits_{i=1}^n a_i \cdot B_i \right ) \mod P

Данный подход для восстановления A является популярным и действенным, однако обладает рядом недостатков. Во-первых мы в сразу же переносимся от действий с маленькими числами к действиям с длинными, так как B_i при выборе предельно больших p_i выходит за диапазон, задаваемый разрядностью вычислений. Во-вторых такой подход предполагает выполнение операции "остаток от деления" по модулю P, который может являться числом очень большим, что приводи к крайне высоким требованиям к ресурсам. Несмотря на это в случае чисел небольшого размера данный метод восстановления остается очень эффективным и простым в реализации. Однако в случае работы с числами большой разрядности его обычно не используют, предпочитая альтернативы и модификации. О некоторых из таких модификаций пойдет речь далее.

Применение обобщенной позиционной системы счисления

Обобщенную позиционную систему счисления (ОПСС) еще называют смешанной. В иностранной литературе алгоритмы, включающие в себя использование этой системы, именуются с использованием словосочетания Mixed Radix (например, Mixed Radix Conversion, MRC). Сама ОПСС строится на тех же самых принципах, что и обычные, позиционные системы счисления, только вместо одного основания в ней используется набор оснований  [3].

Рассмотрим традиционную систему счисления с основанием b. Некоторое число в ней может быть представлено последовательностью разрядов: A=[a_m, a_{m-1}, ..., a_1, a_0]. Тогда представление о величине числа можно получить на основании формулы:

A=a_0 \cdot b^0 + a_1 \cdot b^1 + ... + a_{m-1} \cdot b^{m-1} + a_m \cdot b^m

Определим теперь смешанную систему следующим образом. Пусть набор \pi_1, \pi_2, ..., \pi_m является системой оснований данной ОПСС. Тогда число в ней представляется набором разрядов A=[\alpha_m, \alpha_{m-1}, ..., \alpha_1, \alpha_0], информацию о величине которого можно получить на основании формулы:

A=\alpha_0 + \alpha_1 \cdot \pi_1 + \alpha_2 \cdot \pi_1 \cdot \pi_2+ ... + \alpha_i \cdot \prod \limits_{j=1}^i \pi_j + ... + \alpha_m \cdot \prod \limits_{j=1}^m \pi_j

Если добавить в данную систему \pi_0=1, то ее можно представить как расширение традиционной системы. Обычная позиционная система с основанием b сводится к смешанной путем следующего выбора оснований ОПСС: \pi_0=1, \pi_1=b, \pi_2=b^2, ..., \pi_i=b^i, ..., \pi_m=b^m, .... Основным отличием данных систем является ограниченность ОПСС: для представления чисел, выходящих за диапазон (равный произведению всех оснований), необходимо добавлять новые основания в систему. В традиционной системе счисления это делается очень легко: мы просто берем основание в следующей степени.

Теперь зададимся вопросом: как перевести число из СОК с модулями p_1, p_2, ..., p_n в ОПСС с теми же самими модулями? Оказывается, все относительно просто. Во-первых заранее вычислим матрицу коэффициентов:

\begin{bmatrix}0 & \tau_{1,2} & \tau_{1,3} & ... & \tau_{1,n}\\0 & 0 & \tau_{2,3} & ... & \tau_{2,n}\\& & \vdots & & \\0 & 0 & 0 & ... & \tau_{n-1,n}\end{bmatrix}

Каждую из констант-коэффициентов данной матрицы можно вычислить согласно формуле: \tau_{i,j} = p_i^{-1} \mod p_j (обратные элементы по умножению в кольце классов вычетов). Зная все эти константы, легко перейти от числа A=(a_1,a_2, ..., a_n), представленного в СОК, к числу A=[\alpha_n, \alpha_{n-1}, ..., \alpha_2, \alpha_1], представленному в ОПСС с теми же модулями, основываясь на следующих формулах:

\alpha_1 = a_1,

\alpha_2 = (a_2 - \alpha_1) \cdot \tau_{1,2} \mod p_2,

\alpha_2 = \left ( (a_3 - \alpha_1) \cdot \tau_{1,3} - \alpha_2 \right ) \cdot \tau_{2,3} \mod p_3,

...

\alpha_n = \left (\left ( ... (a_n - \alpha_1) \cdot \tau_{1,n} - \alpha_2 \right ) \cdot \tau_{2,n} - ... - \alpha_{n-1} \right ) \cdot \tau_{n-1,n} \mod p_n

Информацию о позиции числа легко получить на основе знания его представления в ОПСС. Но при необходимости число из ОПСС можно перевести и в традиционную систему пользуясь ранее введенными формулами. Процесс перевода в ОПСС может быть легко распараллелен.

Дальнейшая оптимизация

Наибольший интерес в последнее время представляют два способа упростить вычисления позиционного значения числа по его модулярному виду. Первый заключается в том, что ортогональные базисы представляются сразу в ОПСС [5]. Применение формулы на основе КТО в таком случае приведет к избавлению от операции вычисления остатка по большому модулю, что значительно упростит вычисления.

Другой способ оптимизации [6] заключается в вычислении приближенного значения величины \frac{A}{P}. Данный метод заключается в том, что ортогональные базисы в формуле КТО заменяются относительными величинами: \frac{B_i}{P}. Все вычисления производятся с одним лишь уточнением: вместо операции остаток от деления на P мы просто отбрасываем целую часть. Вновь избавившись от трудоемкой операции, мы переходим к более простым и быстрым вычислениям путем использования длинной арифметики для представления дробной части.

В данной статье я попытался дать краткий обзор основных подходов для организации перевода чисел в и из СОК. Именно описанные методы лежат в основе большинства остальных и без них невозможно представить любой алгоритм, основанный на системе остаточных классов.

Литература

  1. Knuth D. E. The Art of Computer Programming. Vol. 2. Seminumerical Algorithms, Third Edition. – Addison-Wesley, 1998.
  2. Генри Уоррен мл. Алгоритмические трюки для программистов. -Издательский дом Вильямс, 2007.
  3. Червяков Н. И., Сахнюк П. А., Шапошников А. В., Макоха А. Н. Нейрокомпьютеры в остаточных классах. – М.: Радиотехника, 2003. – 272 с.
  4. Акушский И.Я., Юдицкий Д.И. Машинная арифметика в остаточных классах. - М:"Советское радио", 1968.
  5. Червяков Н.И., Бабенко М.Г., Ляхов П.А., Лавриненко И.Н Эффективный алгоритм точного определения универсальной позиционной характеристики модулярных чисел и его применение для вычисления основных проблемных операций в системе остаточных классов // Инфокоммуникационные технологии. 2014.  Т. 12, №1. С. 4-18.
  6. Червяков Н.И., Авербух В.М., Бабенко М.Г., Ляхов П.А., Гладков А.В., Гапочкин А.В. Приближенный метод выполнения немодульных операций в системе остаточных классов. // Фундаментальные исследования, №6, 2012.

One comment on “Перевод чисел между системами счисления

  1. Pingback: Разделение секрета с использованием СОК ← Максим Дерябин

Leave a Reply


Add your ORCID here. (e.g. 0000-0002-7299-680X)