Процедура преобразования чисел из одной системы счисления остаточных классов в другую, учитывающая всевозможные отличия
ART 85259
Автор:
Ш.
Г. Магомедов
Ш.
Г. Магомедов Библиографическое описание статьи для цитирования:
Магомедов
Ш.
Г. Процедура преобразования чисел из одной системы счисления остаточных классов в другую, учитывающая всевозможные отличия // Научно-методический электронный журнал «Концепт». –
2015. – Т. 13. – С.
1291–1295. – URL:
http://e-koncept.ru/2015/85259.htm.
Аннотация. Одним из этапов обработки чисел в модулярной арифметике, который в наибольшей степени требует затрат машинных ресурсов и тем самым значимо понижает эффективность использования методов модулярной арифметики в качестве технологии обработки числовых данных в средствах вычислительной техники, является этап преобразования чисел из позиционной системы счисления (ПСС) в модулярную и наоборот. Как отмечено в [1, 2], при обработке числовых данных часто достаточно иметь алгоритмы преобразования не из модулярной в позиционную, а из одной модулярной системы (с одним основанием) в другую модулярную систему. При этом при определенных условиях преобразования чисел из одной модулярной системы в другую могут оказаться более быстрыми, чем из модулярной в ПС, особенно если количество чисел в основании системы остаточных классов (СОК) достаточно велико. Отметим, что, если количество чисел в основании мало, вычисления в СОК по трудоемкости сравнимы с вычислениями в ПСС. Кроме того, как отмечено в [1], необходимость преобразования представления числа из одной СОК в другую возникает также при необходимости создания определенных условий по обеспечению информационной безопасности процесса обработки данных, так как при длительном использовании одной и той же СОК злоумышленник может путем накопления определенной статистики раскрыть набор чисел, входящих в ее основание. Наконец, при использовании технологий параллельной обработки данных (например, в многопроцессорных системах) на разных процессорах будут сформированы разные основания СОК, и при необходимости использования результатов, полученных на одних процессорах, другими процессорами также возникает необходимость преобразования из одной СОК в другую. Указанной задаче преобразования числовых данных из одной модулярной системы в другую и посвящена данная работа. Публикаций по исследуемой тематике нет. Близкие результаты приведены в [3].
Ключевые слова:
модулярная арифметика, позиционная система счисления, обработка числовых данных, процедура преобразования
Текст статьи
Магомедов Шамиль Гасангусейнович,
кандидат технических наук, старший преподаватель кафедры Программное обеспечение вычислительной техники и автоматизированных систем» ФГБОУ ВПО Дагестанский государственный технический университет», г.Махачкалаmsgg@list.ru
Процедура преобразования чисел из одной системы счисления остаточных классов в другую, учитывающая всевозможные отличия
Аннотация. Одним из этапов обработки чисел в модулярной арифметике, который в наибольшей степени требует затрат машинных ресурсов и тем самым значимо понижает эффективность использования методов модулярной арифметики в качестве технологии обработки числовых данных в средствах вычислительной техники, является этап преобразования чисел из позиционной системы счисления (ПСС) в модулярную и наоборот. Как отмечено в [1, 2], при обработке числовых данных часто достаточно иметь алгоритмы преобразования не из модулярной в позиционную, а из одной модулярной системы (с одним основанием) в другую модулярную систему. При этом при определенных условиях преобразования чисел из одной модулярной системы в другую могут оказаться более быстрыми, чем из модулярной в ПС, особенно если количество чисел в основании системы остаточных классов (СОК) достаточно велико. Отметим, что если количество чисел в основании мало, вычисления в СОК по трудоемкости сравнимы с вычислениями в ПСС. Кроме того, как отмечено в [1], необходимость преобразования представления числа из одной СОК в другую возникает также при необходимости создания определенных условий по обеспечению информационной безопасности процесса обработки данных, т. к. при длительном использовании одной и той же СОК злоумышленник может путем накопления определенной статистики раскрыть набор чисел, входящих в ее основание. Наконец, при использовании технологий параллельной обработки данных (например, в многопроцессорных системах) на разных процессорах будут сформированы разные основания СОК, и при необходимости использования результатов, полученных на одних процессорах, другими процессорами также возникает необходимость преобразования из одной СОК в другую.Указанной задаче преобразования числовых данных из одной модулярной системы в другую и посвящена данная работа. Публикаций по исследуемой тематике нет. Близкие результаты приведены в [3].Ключевые слова: модулярная арифметика, позиционная система счисления, обработка числовых данных, процедура преобразования.Приведем формализованную постановку задачи. Пусть имеются две СОК: A={, , …, }и B= {, , …, }, где и простые числа, и задано некоторое число x, удовлетворяющее условиям , , которое имеет следующие представления в системах Aи B: и . Необходимо построить процедуру, которая позволяла бы, когда известно представление , получить представление непосредственно, без преобразования xAв исходное число xи последующего разложения xв системе B. Положим .Предположим вначале, что K= L. Тогда предлагаемая процедура состоит из отдельных этапов, на каждом из которых в СОК одно из чисел Piзаменяется на одно из чисел Qj, а также подправляется» представление числа xв новой СОК. Описываемая процедура не зависит от порядка следования чисел в основаниях СОК.Рассмотрим первый этап процедуры. Необходимо, имея представление xA=xA (1) в СОК A= A1, получить представление xA(2) числа xв СОК A2={, , , …, }, где
представление числа xв СОК Ai, которые формируются в процессе реализации процедуры. Для получения искомого представления воспользуемся формулой, выражающей искомое число xчерез его разложение в СОК A1[2]:, где , есть решение сравнения (). (1)Пусть в СОК A2число xпредставляется в виде , где для i 1 и ,
есть решение сравнения () и . Последние соотношения равносильны следующим (i � 1):
; (2)Где использовано обозначение , . Первое соотношение в (2) можно переписать в виде или , где . Сравнивая последнее соотношение со вторым соотношением в (2), заключаем:
для всех i� 1. (3)Для нахождения воспользуемся соотношением (1); с учетом (3) получаем, откуда
. (4)При этом, поскольку , то
т. е.
делится на .Вычислив обе части (4) по и воспользовавшись тем, что , получаем соотношение (напомним, ):
. (5)Заметим, что , и
. (6)Соотношения (5) и (6) позволяют вычислить число без вычисления числа x.Аналогичным образом, на jм шаге алгоритма (), можно получить следующие соотношения для вычисления числа для случая, когда количество чисел в основании СОК при замене одной СОК на другую остается неизменным, т. е. K= L:
, (7)где
; для всех i� j; для ij; (8)
; . (9)Рассмотрим теперь случай LK, т. е. в новойСОК в основании больше чисел, чем в исходной. Введем в основание Aновое простое число Q; получим новую систему оснований . Найдем представление числа xв системе оснований Bна основе его представления в системе оснований A. Рассмотрим вначале случай, когда K= L 1, т. е. система оснований Bполучается из системы оснований Aпутем добавления некоторого простого числа Q, не совпадающего с другими числами основания A: для всех . Тогда справедливы соотношения:, где , , есть решение сравнения (), для и , есть решение сравнения () и . Тогда справедливы соотношения: , откуда после сравнения с соотношением заключаем, что . Отсюда вытекает соотношение
, . (10)Далее, , откуда выводим:
. (11)Соотношения (10), (11) позволяют получить представление числа xв СОК Bна основе его представления в СОК Aв случае, когда K= L 1. В случае K�L+ 1 можно выполнить описанную процедуру KLраз, добавляя на каждом шаге по одному простому числу из тех, которые входят в основание B, но не входят в основание A. Таким образом, процедура получения представления числа xв СОК Bна основе его представления в СОК Aпри K� Lпостроена.Пусть теперь KL, т. е. основание Bполучается из основания Aпутем выбрасывания LKчисел. Рассмотрим вначале случай L= K+ 1 и предположим, что выбрасывается . Тогда, обозначая, как и выше, волной над буквенным обозначением значение соответствующего параметра в СОК с основанием B, имеем: , , , откуда после сравнения последних двух соотношений заключаем:
, ; . (12)Соотношение (12) позволяет получить представление числа xв основании Bпри любых Kи Lпутем выполнения LKшагов, на каждом из которых выбрасывается одно из чисел из основания A.Таким образом, выше получены все необходимые соотношения для получения представления числа xв заданной СОК Bна основе наличия его представления в другой СОК A(при условии, что число xменьше числа, равного произведению чисел в основании каждой из СОК). В следующем разделе описана непосредственно алгоритмическая процедура выполнения указанного преобразования. Как уже отмечалось выше, одним из важных достоинств приведенных соотношений является то, что эти соотношения позволяют получить представление в альтернативной СОК на основе представления в исходной СОК непосредственно, без вычисления самого числа, представлениями которого они являются. Предлагаемый алгоритм имеет еще одно важное достоинство. Напомним, что получение исходного числа на его представления в СОК обычно осуществляется на основе китайской теоремы об остатках, одно из основных соотношений которой приведено в (1). Непосредственное использование (1) требует решения сравнений, что обычно осуществляется на основе обобщенного алгоритма Эвклида. Многократная реализация алгоритма Эвклида и является наиболее трудоемким этапом нахождения представлений чисел в СОК и обратного преобразования представлений в СОК в искомые числа. Предлагаемые соотношения позволяют избежать использования алгоритма Эвклида непосредственно в процессе выполнения преобразований, что существенно повысит скорость реализации процедуры. Именно в приведенных соотношениях алгоритм Эвклида необходим только для получения чисел . Но база данных простых чисел, которые будут использованы при формировании основания СОК, выбирается заранее. Поэтому, заранее, например еще на этапе проектирования системы (процессора), может быть сформирована база данных (таблица) чисел для всех пар чисел и , и в дальнейшем при использовании соотношений (7)(9) эти числа просто могут выбираться из построенной таблицы. Более того, использование таблиц позволяет в значительной мере аппаратно реализовать процесс преобразованиячисел из одной СОК в другую.Таким образом, анализ показывает, что использование соотношений (7)(9) потенциально позволит существенно повысить эффективность преобразования чисел из одной СОК в другую и тем самым повысить быстродействие процессов и процедур вычислений в СОК.
Этапы алгоритма преобразования числа из одной системы остаточных классов в другуюСоотношения (7)(12) позволяют сформировать следующую алгоритмическую процедуру преобразования представления чисел из одной СОК в другую.Шаг 0. На предварительном этапе, предшествующем процессу вычислений (возможно, даже на стадии проектирования процессора), формируется база простых чисел и таблица чисел для всех пар простых чисел Pи Q() из сформированной базы простых чисел. Шаг 1.Вводится число xи выбирается некоторая система оснований СОК A={, , …, }из простых чисел (которые все различны и упорядочены по возрастанию) из базы простых чисел. При этом число Lи числа Piвыбираются так, чтобы выполнялось условие . Строится представление числа xв СОК с основанием Aследующим образом: , где (). Необходимо перейти к представлению числа xв СОК с другой системой оснований B={, , …, }, т. е. получить представление , где . Находим числа для всех .Шаг 2.Сравниваются числа Kи L.Если LK, то переходим к шагу 6. В противном случае (т. е. ) последовательно для jот 1 до Kвыполняются следующие действия.Шаг 3.Число Pjсравнивается с числами Qi, входящими в основание B. Если найдется число mтакое, что Pj= Qm, то число jувеличиваем на единицу. Если полученное значение j= K, то переходим к шагу 5. В противном случае переходим к началу шага 3. Если же для всех , то выполняются следующие действия.Шаг 4.Находим на основе равенств (7)(9) числа и , для всех iот 1 до L. Увеличиваем jна единицу и проверяем условие j= K. Если оно выполняется, то переходим к шагу 5, предварительно присваивая значения , для всех . В противном случае переходим к шагу 3.Шаг 5.При L= Kпереходим к шагу 6. В противном случае (т. е. L� K) последовательно для jот Lдо K+ 1 выполняются следующие действия. Вначале полагаем j= L.На основе (12) находятся значения коэффициентов , для всех ij. Значение jуменьшается на единицу; если полученное значение jравно K+ 1, то процесс вычислений шага 5 прекращается и переходим к следующему шагу 7. Если j� K+ 1, то полагаем , для всех и переходим к началу данного шага (начало данного абзаца).Шаг 6.Если LK, то последовательно выполняются следующие действия. Вначале, аналогично шагу 4, на основе равенств (7)(9) находим числа и , для всех iот 1 до L. Затем последовательно для jот L+ 1 до Kвыполняются следующие действия. Вначале полагаем j= L+ 1. На основе соотношения (10) находятся коэффициенты , для всех ij; на основе соотношения (11) находится и . Далее увеличиваем jна единицу. Если выполняется равенство j= K, то переходим к следующему шагу. В противном случае полагаем , для всех и переходим к началу шага 6 (начало данного абзаца).Шаг 7.Выводится вектор в качестве представления числа xв СОК с основанием B, а также запоминаются вспомогательные коэффициенты , для всех iот 1 до Kдля их использования при последующих вычислениях.Процесс вычислений заканчивается.На основе описанной процедуры может быть разработан алгоритм, ориентированный непосредственно на написание программного кода.
Реализация разработанного алгоритма Для практической реализации разработанного алгоритма необходимо оценить возможные значения приведенных выше параметров алгоритма, в частности количество чисел в основании СОК; ограничения на числа, входящие в основание; количество простых чисел в базе данных; размеры таблицы обратных значений простых чисел в модульной арифметике. Перечисленные вопросы ниже рассматриваются с точки зрения возможностей современных типовых процессоров, поскольку разработанный алгоритм может представлять большой интерес применительно к организации работы процессоров. Рассмотрим четырехъядерный процессор, каждое ядро которого может обрабатывать числа длиной 64 бит. Оценим вначале число Lпростых чисел в основании. Так как , то при L� 4среди чисел найдутся числа, удовлетворяющие соотношению достаточно малые числа, которые при наборе определенной подходящей статистики могут быть взломаны злоумышленником, что существенно облегчит ему возможности по нахождению других чисел в основании СОК. При L4 количество чисел в основании достаточно мало, что усложняет текущие вычисления в СОК, делая их по трудоемкости сравнимыми с вычислениями в позиционной системе. На основании вышесказанногопредлагается каждому ядру сопоставить СОК с четырьмя простыми числами в основании, т. е. L= 4. Для того чтобы простые числа трудно было подобрать (например, путем перебора), предлагается наложить ограничения на минимальную длину простых чисел, а именно предлагается выбрать простые числа Pi(i= 1, 2, 3, 4), удовлетворяющие условию Pi� 214= 8192.Поскольку при этом произведение P1· P2·P3· P4является верхней границей для обрабатываемых чисел, то получаем оценку 264P1· P2·P3· P4. При этом желательно, чтобы разница между правой и левой частями была бы как можно меньше для неизбыточностивычислений. Отсюда выводим, что каждое из чисел Piне должно быть очень большим, т. к. в противном случае не удастся обеспечить выполнение условия Pi� 214для всех i.Поэтому для максимально возможных значений простого числа Pв основании СОК получаем соотношение , откуда выводим соотношение . Таким образом, получаем следующие ограничения на величины простых чисел Pв основании СОК: 214P222.Оценим теперь размер таблицы обратных значений P(Q)для всех парпростых чисел. По теореме Чебышева, при достаточно больших nколичество простых чисел, не превосходящих n, асимптотически эквивалентно . Отсюда выводим, что количество простых чисел P, удовлетворяющих условию 214P222, приблизительно равно.Следовательно, размер таблицы (т. е. количество заполняемых клеток) приблизительно равен чисел. Оценим величину времени, необходимого для заполнения таблицы. Оценки показывают, что вычисление одного значения таблицы обратных величин на основе обобщенного алгоритма Эвклида требует не более тактовых операций. Тогда при использовании процессора с тактовой частотой 2 ГГц = 2 ∙ 230 Гц потребуется времени порядка
Поскольку таблица формируется заранее (не в режиме реального времени), то затраты времени порядка 18 часов на заполнение таблицы вполне приемлемы.Из приведенного анализа заключаем, что предлагаемая процедура преобразования чисел из одной СОК в другую практически реализуема с точки зрения возможностей существующих вычислительных устройств.
Заключение1. Получены математические соотношения, позволяющие на основе представлений числа в одной СОК находить его представления в другой без использования алгоритма Эвклида и вычисления искомого числа в процессе преобразований, что существенно повышает скорость выполнения операции преобразования. 2. На основе полученных математических соотношений сформирована алгоритмическая процедура преобразования чисел из одной СОК в другую, учитывающая всевозможные отличия между двумя СОК как по количеству чисел в основании каждой СОК, так и по их составу.3. Произведена оценка основных характеристик процесса преобразования с учетом возможностей современных процессоров, что позволило сделать вывод о возможности практической реализации разработанной процедуры.Рассматриваемый этап использования СОК в процессе обработки числовой информации связан с одним из наиболее трудоемких этапов обработки, поэтому практическая реализация приведенного алгоритма позволит значимо повысить эффективность использования СОК в системах обработки данных, в частности в микропроцессорных устройствах.
Ссылки на источники1.Магомедов Ш. Г.Формирование состава макрокоманд микропроцессора с вычислительной базой
на основе системы остаточных классов / Ш. Г. Магомедов, Г. А. Попов, В. П. Шевчук // Вестн. Астрахан. гос. техн. унта. Сер.: Управление, вычислительная техника и информатика. 2014. № 2. С. 3844.2.Магомедов Ш. Г.Алгоритм и схема сложения чисел в арифметикологическом устройстве с использованием системы остаточных классов / Ш. Г. Магомедов // Вестн. Астрахан. гос. техн. унта. Сер.: Управление, вычислительная техника и информатика. 2014. № 1. С. 6268.3.Эрдниева Н. С.Использование специальных модулей системы остаточных классов для избыточного представления / Н. С. Эрдниева// Вестн.Астрахан. гос. техн. унта. Сер.: Управление, вычислительная техника и информатика. 2013. № 2. С. 7585.
кандидат технических наук, старший преподаватель кафедры Программное обеспечение вычислительной техники и автоматизированных систем» ФГБОУ ВПО Дагестанский государственный технический университет», г.Махачкалаmsgg@list.ru
Процедура преобразования чисел из одной системы счисления остаточных классов в другую, учитывающая всевозможные отличия
Аннотация. Одним из этапов обработки чисел в модулярной арифметике, который в наибольшей степени требует затрат машинных ресурсов и тем самым значимо понижает эффективность использования методов модулярной арифметики в качестве технологии обработки числовых данных в средствах вычислительной техники, является этап преобразования чисел из позиционной системы счисления (ПСС) в модулярную и наоборот. Как отмечено в [1, 2], при обработке числовых данных часто достаточно иметь алгоритмы преобразования не из модулярной в позиционную, а из одной модулярной системы (с одним основанием) в другую модулярную систему. При этом при определенных условиях преобразования чисел из одной модулярной системы в другую могут оказаться более быстрыми, чем из модулярной в ПС, особенно если количество чисел в основании системы остаточных классов (СОК) достаточно велико. Отметим, что если количество чисел в основании мало, вычисления в СОК по трудоемкости сравнимы с вычислениями в ПСС. Кроме того, как отмечено в [1], необходимость преобразования представления числа из одной СОК в другую возникает также при необходимости создания определенных условий по обеспечению информационной безопасности процесса обработки данных, т. к. при длительном использовании одной и той же СОК злоумышленник может путем накопления определенной статистики раскрыть набор чисел, входящих в ее основание. Наконец, при использовании технологий параллельной обработки данных (например, в многопроцессорных системах) на разных процессорах будут сформированы разные основания СОК, и при необходимости использования результатов, полученных на одних процессорах, другими процессорами также возникает необходимость преобразования из одной СОК в другую.Указанной задаче преобразования числовых данных из одной модулярной системы в другую и посвящена данная работа. Публикаций по исследуемой тематике нет. Близкие результаты приведены в [3].Ключевые слова: модулярная арифметика, позиционная система счисления, обработка числовых данных, процедура преобразования.Приведем формализованную постановку задачи. Пусть имеются две СОК: A={, , …, }и B= {, , …, }, где и простые числа, и задано некоторое число x, удовлетворяющее условиям , , которое имеет следующие представления в системах Aи B: и . Необходимо построить процедуру, которая позволяла бы, когда известно представление , получить представление непосредственно, без преобразования xAв исходное число xи последующего разложения xв системе B. Положим .Предположим вначале, что K= L. Тогда предлагаемая процедура состоит из отдельных этапов, на каждом из которых в СОК одно из чисел Piзаменяется на одно из чисел Qj, а также подправляется» представление числа xв новой СОК. Описываемая процедура не зависит от порядка следования чисел в основаниях СОК.Рассмотрим первый этап процедуры. Необходимо, имея представление xA=xA (1) в СОК A= A1, получить представление xA(2) числа xв СОК A2={, , , …, }, где
представление числа xв СОК Ai, которые формируются в процессе реализации процедуры. Для получения искомого представления воспользуемся формулой, выражающей искомое число xчерез его разложение в СОК A1[2]:, где , есть решение сравнения (). (1)Пусть в СОК A2число xпредставляется в виде , где для i 1 и ,
есть решение сравнения () и . Последние соотношения равносильны следующим (i � 1):
; (2)Где использовано обозначение , . Первое соотношение в (2) можно переписать в виде или , где . Сравнивая последнее соотношение со вторым соотношением в (2), заключаем:
для всех i� 1. (3)Для нахождения воспользуемся соотношением (1); с учетом (3) получаем, откуда
. (4)При этом, поскольку , то
т. е.
делится на .Вычислив обе части (4) по и воспользовавшись тем, что , получаем соотношение (напомним, ):
. (5)Заметим, что , и
. (6)Соотношения (5) и (6) позволяют вычислить число без вычисления числа x.Аналогичным образом, на jм шаге алгоритма (), можно получить следующие соотношения для вычисления числа для случая, когда количество чисел в основании СОК при замене одной СОК на другую остается неизменным, т. е. K= L:
, (7)где
; для всех i� j; для ij; (8)
; . (9)Рассмотрим теперь случай LK, т. е. в новойСОК в основании больше чисел, чем в исходной. Введем в основание Aновое простое число Q; получим новую систему оснований . Найдем представление числа xв системе оснований Bна основе его представления в системе оснований A. Рассмотрим вначале случай, когда K= L 1, т. е. система оснований Bполучается из системы оснований Aпутем добавления некоторого простого числа Q, не совпадающего с другими числами основания A: для всех . Тогда справедливы соотношения:, где , , есть решение сравнения (), для и , есть решение сравнения () и . Тогда справедливы соотношения: , откуда после сравнения с соотношением заключаем, что . Отсюда вытекает соотношение
, . (10)Далее, , откуда выводим:
. (11)Соотношения (10), (11) позволяют получить представление числа xв СОК Bна основе его представления в СОК Aв случае, когда K= L 1. В случае K�L+ 1 можно выполнить описанную процедуру KLраз, добавляя на каждом шаге по одному простому числу из тех, которые входят в основание B, но не входят в основание A. Таким образом, процедура получения представления числа xв СОК Bна основе его представления в СОК Aпри K� Lпостроена.Пусть теперь KL, т. е. основание Bполучается из основания Aпутем выбрасывания LKчисел. Рассмотрим вначале случай L= K+ 1 и предположим, что выбрасывается . Тогда, обозначая, как и выше, волной над буквенным обозначением значение соответствующего параметра в СОК с основанием B, имеем: , , , откуда после сравнения последних двух соотношений заключаем:
, ; . (12)Соотношение (12) позволяет получить представление числа xв основании Bпри любых Kи Lпутем выполнения LKшагов, на каждом из которых выбрасывается одно из чисел из основания A.Таким образом, выше получены все необходимые соотношения для получения представления числа xв заданной СОК Bна основе наличия его представления в другой СОК A(при условии, что число xменьше числа, равного произведению чисел в основании каждой из СОК). В следующем разделе описана непосредственно алгоритмическая процедура выполнения указанного преобразования. Как уже отмечалось выше, одним из важных достоинств приведенных соотношений является то, что эти соотношения позволяют получить представление в альтернативной СОК на основе представления в исходной СОК непосредственно, без вычисления самого числа, представлениями которого они являются. Предлагаемый алгоритм имеет еще одно важное достоинство. Напомним, что получение исходного числа на его представления в СОК обычно осуществляется на основе китайской теоремы об остатках, одно из основных соотношений которой приведено в (1). Непосредственное использование (1) требует решения сравнений, что обычно осуществляется на основе обобщенного алгоритма Эвклида. Многократная реализация алгоритма Эвклида и является наиболее трудоемким этапом нахождения представлений чисел в СОК и обратного преобразования представлений в СОК в искомые числа. Предлагаемые соотношения позволяют избежать использования алгоритма Эвклида непосредственно в процессе выполнения преобразований, что существенно повысит скорость реализации процедуры. Именно в приведенных соотношениях алгоритм Эвклида необходим только для получения чисел . Но база данных простых чисел, которые будут использованы при формировании основания СОК, выбирается заранее. Поэтому, заранее, например еще на этапе проектирования системы (процессора), может быть сформирована база данных (таблица) чисел для всех пар чисел и , и в дальнейшем при использовании соотношений (7)(9) эти числа просто могут выбираться из построенной таблицы. Более того, использование таблиц позволяет в значительной мере аппаратно реализовать процесс преобразованиячисел из одной СОК в другую.Таким образом, анализ показывает, что использование соотношений (7)(9) потенциально позволит существенно повысить эффективность преобразования чисел из одной СОК в другую и тем самым повысить быстродействие процессов и процедур вычислений в СОК.
Этапы алгоритма преобразования числа из одной системы остаточных классов в другуюСоотношения (7)(12) позволяют сформировать следующую алгоритмическую процедуру преобразования представления чисел из одной СОК в другую.Шаг 0. На предварительном этапе, предшествующем процессу вычислений (возможно, даже на стадии проектирования процессора), формируется база простых чисел и таблица чисел для всех пар простых чисел Pи Q() из сформированной базы простых чисел. Шаг 1.Вводится число xи выбирается некоторая система оснований СОК A={, , …, }из простых чисел (которые все различны и упорядочены по возрастанию) из базы простых чисел. При этом число Lи числа Piвыбираются так, чтобы выполнялось условие . Строится представление числа xв СОК с основанием Aследующим образом: , где (). Необходимо перейти к представлению числа xв СОК с другой системой оснований B={, , …, }, т. е. получить представление , где . Находим числа для всех .Шаг 2.Сравниваются числа Kи L.Если LK, то переходим к шагу 6. В противном случае (т. е. ) последовательно для jот 1 до Kвыполняются следующие действия.Шаг 3.Число Pjсравнивается с числами Qi, входящими в основание B. Если найдется число mтакое, что Pj= Qm, то число jувеличиваем на единицу. Если полученное значение j= K, то переходим к шагу 5. В противном случае переходим к началу шага 3. Если же для всех , то выполняются следующие действия.Шаг 4.Находим на основе равенств (7)(9) числа и , для всех iот 1 до L. Увеличиваем jна единицу и проверяем условие j= K. Если оно выполняется, то переходим к шагу 5, предварительно присваивая значения , для всех . В противном случае переходим к шагу 3.Шаг 5.При L= Kпереходим к шагу 6. В противном случае (т. е. L� K) последовательно для jот Lдо K+ 1 выполняются следующие действия. Вначале полагаем j= L.На основе (12) находятся значения коэффициентов , для всех ij. Значение jуменьшается на единицу; если полученное значение jравно K+ 1, то процесс вычислений шага 5 прекращается и переходим к следующему шагу 7. Если j� K+ 1, то полагаем , для всех и переходим к началу данного шага (начало данного абзаца).Шаг 6.Если LK, то последовательно выполняются следующие действия. Вначале, аналогично шагу 4, на основе равенств (7)(9) находим числа и , для всех iот 1 до L. Затем последовательно для jот L+ 1 до Kвыполняются следующие действия. Вначале полагаем j= L+ 1. На основе соотношения (10) находятся коэффициенты , для всех ij; на основе соотношения (11) находится и . Далее увеличиваем jна единицу. Если выполняется равенство j= K, то переходим к следующему шагу. В противном случае полагаем , для всех и переходим к началу шага 6 (начало данного абзаца).Шаг 7.Выводится вектор в качестве представления числа xв СОК с основанием B, а также запоминаются вспомогательные коэффициенты , для всех iот 1 до Kдля их использования при последующих вычислениях.Процесс вычислений заканчивается.На основе описанной процедуры может быть разработан алгоритм, ориентированный непосредственно на написание программного кода.
Реализация разработанного алгоритма Для практической реализации разработанного алгоритма необходимо оценить возможные значения приведенных выше параметров алгоритма, в частности количество чисел в основании СОК; ограничения на числа, входящие в основание; количество простых чисел в базе данных; размеры таблицы обратных значений простых чисел в модульной арифметике. Перечисленные вопросы ниже рассматриваются с точки зрения возможностей современных типовых процессоров, поскольку разработанный алгоритм может представлять большой интерес применительно к организации работы процессоров. Рассмотрим четырехъядерный процессор, каждое ядро которого может обрабатывать числа длиной 64 бит. Оценим вначале число Lпростых чисел в основании. Так как , то при L� 4среди чисел найдутся числа, удовлетворяющие соотношению достаточно малые числа, которые при наборе определенной подходящей статистики могут быть взломаны злоумышленником, что существенно облегчит ему возможности по нахождению других чисел в основании СОК. При L4 количество чисел в основании достаточно мало, что усложняет текущие вычисления в СОК, делая их по трудоемкости сравнимыми с вычислениями в позиционной системе. На основании вышесказанногопредлагается каждому ядру сопоставить СОК с четырьмя простыми числами в основании, т. е. L= 4. Для того чтобы простые числа трудно было подобрать (например, путем перебора), предлагается наложить ограничения на минимальную длину простых чисел, а именно предлагается выбрать простые числа Pi(i= 1, 2, 3, 4), удовлетворяющие условию Pi� 214= 8192.Поскольку при этом произведение P1· P2·P3· P4является верхней границей для обрабатываемых чисел, то получаем оценку 264P1· P2·P3· P4. При этом желательно, чтобы разница между правой и левой частями была бы как можно меньше для неизбыточностивычислений. Отсюда выводим, что каждое из чисел Piне должно быть очень большим, т. к. в противном случае не удастся обеспечить выполнение условия Pi� 214для всех i.Поэтому для максимально возможных значений простого числа Pв основании СОК получаем соотношение , откуда выводим соотношение . Таким образом, получаем следующие ограничения на величины простых чисел Pв основании СОК: 214P222.Оценим теперь размер таблицы обратных значений P(Q)для всех парпростых чисел. По теореме Чебышева, при достаточно больших nколичество простых чисел, не превосходящих n, асимптотически эквивалентно . Отсюда выводим, что количество простых чисел P, удовлетворяющих условию 214P222, приблизительно равно.Следовательно, размер таблицы (т. е. количество заполняемых клеток) приблизительно равен чисел. Оценим величину времени, необходимого для заполнения таблицы. Оценки показывают, что вычисление одного значения таблицы обратных величин на основе обобщенного алгоритма Эвклида требует не более тактовых операций. Тогда при использовании процессора с тактовой частотой 2 ГГц = 2 ∙ 230 Гц потребуется времени порядка
Поскольку таблица формируется заранее (не в режиме реального времени), то затраты времени порядка 18 часов на заполнение таблицы вполне приемлемы.Из приведенного анализа заключаем, что предлагаемая процедура преобразования чисел из одной СОК в другую практически реализуема с точки зрения возможностей существующих вычислительных устройств.
Заключение1. Получены математические соотношения, позволяющие на основе представлений числа в одной СОК находить его представления в другой без использования алгоритма Эвклида и вычисления искомого числа в процессе преобразований, что существенно повышает скорость выполнения операции преобразования. 2. На основе полученных математических соотношений сформирована алгоритмическая процедура преобразования чисел из одной СОК в другую, учитывающая всевозможные отличия между двумя СОК как по количеству чисел в основании каждой СОК, так и по их составу.3. Произведена оценка основных характеристик процесса преобразования с учетом возможностей современных процессоров, что позволило сделать вывод о возможности практической реализации разработанной процедуры.Рассматриваемый этап использования СОК в процессе обработки числовой информации связан с одним из наиболее трудоемких этапов обработки, поэтому практическая реализация приведенного алгоритма позволит значимо повысить эффективность использования СОК в системах обработки данных, в частности в микропроцессорных устройствах.
Ссылки на источники1.Магомедов Ш. Г.Формирование состава макрокоманд микропроцессора с вычислительной базой
на основе системы остаточных классов / Ш. Г. Магомедов, Г. А. Попов, В. П. Шевчук // Вестн. Астрахан. гос. техн. унта. Сер.: Управление, вычислительная техника и информатика. 2014. № 2. С. 3844.2.Магомедов Ш. Г.Алгоритм и схема сложения чисел в арифметикологическом устройстве с использованием системы остаточных классов / Ш. Г. Магомедов // Вестн. Астрахан. гос. техн. унта. Сер.: Управление, вычислительная техника и информатика. 2014. № 1. С. 6268.3.Эрдниева Н. С.Использование специальных модулей системы остаточных классов для избыточного представления / Н. С. Эрдниева// Вестн.Астрахан. гос. техн. унта. Сер.: Управление, вычислительная техника и информатика. 2013. № 2. С. 7585.
