Модулярная система счисления (МСС) квадратичного диапазона представляет собой расширение традиционной модулярной системы счисления (одинарного диапазона). МСС предназначена для работы в больших числовых областях и специфическими алгоритмами обработки чисел. Она является математической моделью для реализации вычислений на цифровых вычислительных устройствах.

К основным компонентам МСС квадратичного диапазона относятся следующие.

Элементы этой совокупности представляют собой числа, выраженные в виде вычетов по различным основаниям. Эти основания определяют конкретный диапазон значений, внутри которого проводятся операции над числами. Каждое число записывается в виде остатков от деления на некоторые фиксированные основания – модули.

Операции, выполняемые над представленными в МСС данными, делят на два класса: модульные и немодульные. Модульные характеризуются тем, что при их выполнении не происходит переносов между разрядами. Примерами таких операций являются сложение, вычитание и умножение, деление нацело, умножение на обратный элемент и др. К немодульным операциям отнесены деление, расширение, определение знака, сравнение, определение переполнения, масштабирование, определение ошибки, локализация ошибки, вычисление ранга и др. Для выполнения этих операций, в отличие от модульных, требуется оценка значения числа в целом, которая затруднена в связи с непозиционной природой МСС [1][2].

Алгоритмические процедуры предназначены для оптимизации процесса вычислений, минимизации временных затрат и повышения точности результатов.

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

– двоичная система, которая используется благодаря простоте аппаратной реализации и эффективности хранения информации;

– шестнадцатеричная система применяется, когда нужна компактность представления больших объемов данных и удобство восприятия человеком.

В данном исследовании основные арифметические операции в МСС реализованы на серийном (позиционном) компьютере.

Серийный компьютер – это вычислительная система классической архитектуры, в которой операнды представлены в позиционной системе счисления (ПСС), а операции выполняются последовательно. Термин «серийный» подчеркивает традиционный подход к обработке данных, в отличие от специализированных систем, таких как модулярные компьютеры.

К основным характеристикам серийных компьютеров можно отнести следующие.

Операции в МСС, реализованные на серийном (позиционном) компьютере, сопровождаются рядом трудностей.

Преобразование между системами счисления требует вычислительных ресурсов.

Введем основные понятия и определения для МСС квадратичного диапазона.

В МСС каждое число представляется в виде набора остатков по соответствующим основаниям (модулям), позволяющим эффективно использовать ресурсы оборудования и минимизировать ошибки округления при выполнении сложных расчетов [3].

Стоит отметить, что в статье модули, по которым вычисляются наименьшие неотрицательные вычеты по модулю (остатки от деления), называются в этой тематике основаниями одинарной или квадратичной МСС.

Определение: Модулярная система счисления квадратичного диапазона – это совокупность математических конструкций и правил, предназначенных для представления и обработки чисел с использованием системы взаимно простых модулей, каждый из которых является квадратом простого числа.

Пусть p1, p2, ... pn – простые числа и пусть mi = pi2, i = 1, 2, ..., n – соответствующие квадратичные модули. Тогда любое целое число X в диапазоне [0, M − 1], где M = m1 · m2 · ... · mn, может быть однозначно представлено в виде набора остатков:

X = (a1, a2, ... an) (m1, m2, ... mn),

где ai – остаток от деления числа X на модуль mi, то есть ai = X mod mi; пара a1, a2, ... an называется модулярным представлением числа X.

Определение: Квадратичный модуль – это модуль, задаваемый в виде квадрата простого числа ρ, то есть m = ρ2.

Определение: Диапазон значений – множество чисел, представленных в МСС с квадратичными модулями, ограничено верхним пределом, равным произведению всех модулей.

Китайская теорема об остатках (КТО) – известная в теории чисел. Из теоремы следует: если заданы попарно взаимно простые модули m1, m2, ... mn, то любое число Y в диапазоне [0, M − 1], где M = m1 · m2 · ... · mn, может быть однозначно представлено своими остатками по этим модулям.

Теорема: Пусть m1, m2, ... mn – попарно взаимно простые числа, то есть НОД(mi, mj) = 1 для всех i ≠ j. Тогда система сравнений:

имеет единственное решение Y в диапазоне [0, M − 1], где M = m1 · m2 · ... · mn.

Доказательство.

Пусть модули m1, m2, ... mn попарно взаимно просты, то есть НОД(mi, mj) = 1 для всех i ≠ j. Требуется доказать существование и единственность решения Y в указанном диапазоне. 

Так как модули попарно взаимно просты, очевидно, что Mi и mi также взаимно просты для каждого i.

Для каждого Mi найдем обратный элемент Xi по модулю mi, то есть такое число, что:

(Xi ∙ Mi) ≡ 1(mod mi)

Обратные элементы можно найти с помощью расширенного алгоритма Евклида.

III. Далее воспользуемся формулой:

Рассмотрим арифметические операции в МСС квадратичного диапазона.

Сложение и вычитание в МСС квадратичного диапазона выполняются поэлементно по каждому модулю с последующим вычислением остатка [1][2][4][5]. Пусть заданы два числа A = α1 · α2 · ... · αn и B = β1 · β2 · ... · βn, где αi и βi – остатки по модулям mi = pi2, а pi – простые числа. Тогда:

A + B = (α1 + β1 (mod m1), α2 + β2 (mod m2),…, αn + βn (mod mn)),

A – B = (α1 – β1 (mod m1), α2 – β2 (mod m2),…,αn – βn (mod mn)).

Умножение также выполняется поэлементно с последующим взятием остатка:

A · B = (α1 · β1 (mod m1), α2 · β2 (mod m2),…,αn · βn (mod mn)).

Результаты операций сложения, вычитания и умножения A + B, A – B и A · B представлены остатками γi σi и δi по тем же основаниям системы счисления mi.

A + B = (γ1 , γ2, ... · γn),

A – B = (σ1 , σ2, ... · σn),

A · B = (δ1 , δ2, ... · δn),

где γi сравнимо с αi + βi по модулю mi, σi сравнимо с αi – βi по модулю mi, δi сравнимо с αi · βi по тому же модулю, выполняются соотношения:

γi = αi + βi (mod mi),

σi = αi – βi (mod mi),

δi = αi · βi (mod mi).

Результатом являются числа:

Пример 1. Рассмотрим выполнение данных операций на примере.

В компьютерах, поддерживающих 32-битные числа, типовой диапазон чисел – от 0 до 232 − 1. Ставится задача – выбрать подходящий набор квадратичных модулей, который покроет этот диапазон, и выполнить операции сложения, вычитания и умножения в МСС.

В качестве оснований выберем взаимно простые числа, квадраты которых дадут достаточное покрытие диапазона: m1 = 17, тогда p1 = 172 = 289, m2 = 19, тогда p2 = 19 = 361, m3 = 23, тогда p3 = 232 = 529, m4 = 29, тогда p4 = 292 = 841, m5 = 31,тогда p5 = 312 = 961. М = 289 · 361 · 529 · 841 · 961 = 44604646326241 > 232 − 1 = 4294967295.

Необходимость превышения произведения модулей над машинным диапазоном обусловлена особенностью МCС и требованием полной однозначности представления чисел.

Пусть даны два числа, представленных в МСС: A = (23, 87, 12, 34, 56) и B = (17, 34, 157, 89, 112).

Выполняем поэлементное сложение с последующим взятием остатка по каждому модулю:

A + B = (23 + 17 (mod 289), 87 + 24 (mod 361), 12 + 157 (mod 529), 34 + 89 (mod 841), 56 + 112 (mod 961)) = (40 (mod 289), 121 (mod 361), 169 (mod 529), 1239 (mod 841), 168 (mod 961)) == (40, 121, 169, 123, 168).

Аналогично выполняем поэлементное вычитание со взятием остатка:

A−B = (23−17 (mod 289), 87−24 (mod 361), 12−157 (mod 529), 34−89 (mod 841), 56−112 (mod 961)) = (6 (mod 289), 53 (mod 361), 384 (mod 529), 786 (mod 841), 905 (mod 961)) = = (6, 53, 384, 786, 905).

При выполнении операции вычитания в МСС результатом может оказаться отрицательное число. Однако в МСС работают с неотрицательными числами, ограниченными пределами выбранного модуля. Для перевода результата в стандартный вид применяется простая процедура: если число получилось отрицательным, к нему добавляют модуль. Это обусловлено следующими причинами:

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

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

В МСС каждое число в диапазоне [0, M − 1] должно иметь единственное представление. Появление отрицательного числа нарушает это правило, поэтому нормализация необходима.

Добавление модуля нормализует результат и восстанавливает нормальное состояние системы, позволяя продолжить вычисления без нарушения законов модулярной арифметики.

На примерах выполним поэлементное умножение с последующим взятием остатка:

A · B = (23 · 17 (mod 289), 87 · 34 (mod 361), 12 · 157 (mod 529), 34 · 89 (mod 841), 56 · 112 (mod 961)) = (391 (mod 289), 2958 (mod 361), 1884 (mod 529), 3026 (mod 841), 6272 (mod 961)) = (102, 70, 297, 503, 506).

Возведение в степень в МСС квадратичного диапазона выполняется поэлементно с последующим взятием остатка по каждому модулю.

Пусть A = (23, 87, 12, 34, 56) и k = 5. Необходимо найти Ak.

Для каждого модуля mi возводим соответствующую компоненту числа A в степень k и берем остаток по модулю mi.

A5 = (235 (mod 289), 875 (mod 361), 125 (mod 529), 345 (mod 841), 565 (mod 961)) == (6436343 (mod 289), 4984209207 (mod 361), 248832 (mod 529), 45435424 (mod 841), 550731776 (mod 961)) = (24, 254, 202, 399, 935).

Нахождение обратного числа в МСС квадратичного диапазона выполняется поэлементно с использованием расширенного алгоритма Евклида. Это позволяет эффективно обрабатывать числа и выполнять обратные операции в МСС.

Определение: Обратное число A–1 по модулю mi – это такое число, что: A–1 · A ≡ 1 (mod mi).

Для каждого модуля mi находится обратный элемент Xi для соответствующей компоненты числа A по модулю mi. Будем использовать расширенный алгоритм Евклида для поиска обратных элементов. Рассмотрим его подробно.

Требуется найти обратный элемент Y для числа A по модулю m, то есть такое число Y, что:

A · X ≡ 1 (mod m).

Расширенный алгоритм Евклида основан на классическом алгоритме Евклида для нахождения наибольшего общего делителя (НОД), дополненном поиском коэффициентов Безу.

Алгоритм

Пусть A и m – заданные числа, причем НОД(A, m) = 1 (условие взаимной простоты). Введем начальные значения: x0 = 1, x1 = 0, y0 = 0, y1 = 1.

Пока m ≠ 0, делаем следующие шаги:

Обновляем коэффициенты:

(x0, x1) = ( x1, x0 − q · x1),( y0, y1) = ( y1, y0 − q · y1).

III. Завершение цикла.

Когда m = 0, последний ненулевой остаток A – это НОД. Если A = 1, то обратный элемент найден и равен x0.

Пример 2. Пусть A = (23, 87, 12, 34, 56). Необходимо найти A–1.

Найдем обратный элемент для A = 23 по модулю m = 289.

A = 23, m = 289, x0 = 1, x1 = 0, y0 = 0, y1 = 1.

Первый шаг:

Обновляем коэффициенты:

A = 289, m = 23, x0 = 0, x1 = 1, y0 = 1, y1 = 0.

Второй шаг:

Обновляем коэффициенты:

A = 23, m = 13, x0 = 1, x1 = –12, y0 = 0, y1 = 1.

Третий шаг:

Обновляем коэффициенты:

A = 13, m = 10, x0 = –12, x1 = 13, y0 = 1, y1 = –1.

Четвертый шаг:

Обновляем коэффициенты:

A = 10, m = 3, x0 = 13, x1 = –25, y0 = −1, y1 = 2.

Пятый шаг:

Обновляем коэффициенты:

A = 3, m = 1, x0 = –25, x1 = 88, y0 = −2, y1 = 7.

Последний шаг:

Обновляем коэффициенты:

A = 1, m = 0, x0 = 88, x1 = −299, y0 = −7, y1 = 23.

III. Завершение.

Последний ненулевой остаток A = 1, следовательно, обратный элемент равен x0 = 88.

Расширенный алгоритм Евклида позволил найти обратный элемент к числу 23 по модулю 289, он равен 88.

Чтобы проверить результат, подставим его в исходное уравнение:

A · X ≡ 1 (mod m)

23 · 88 ≡ 1 (mod 289)

Вычислим левую сторону: 23 · 88 = 2024.

Теперь возьмем остаток от деления на 289: 2024 (mod 289) = 1.

Таким образом, уравнение выполняется, и 88 действительно является обратным элементом к 23 по модулю 289.

Аналогично, найдем обратные элементы для остальных компонент числа A = (23, 87, 12, 34, 56) по остальным модулям p2 = 361, p3 = 529, p4 = 841, p5 = 961. Используя расширенный алгоритм Евклида для каждого модуля отдельно, получим:

87 · 83 ≡ 1 (mod 361)

12 · 485 ≡ 1 (mod 529)

34 · 470 ≡ 1 (mod 841)

56 · 532 ≡ 1 (mod 961)

Обратное число для A = (23, 87, 12, 34, 56) по модулям p1 = 289, p2 = 361, p3 = 529, p4 = 841, p5 = 961 соответственно: A−1 = (88, 83, 485, 470, 532).

Рассмотрим отдельно случай для компоненты α5 = 56 числа A, по модулю p5 = 961. Расширенный алгоритм Евклида позволил нам найти, что обратный элемент к числу 56 по модулю 961 равен –429. Однако в модулярной арифметике результат должен находиться в диапазоне от [0, p5 − 1]. В нашем случае модуль равен 961.

Чтобы привести результат к нужному диапазону, мы добавляем модуль к отрицательному числу:

–429 + 961 = 532.

Таким образом, –429 эквивалентно 532 по модулю 961.

Нормализация отрицательного результата путем добавления модуля – это стандартная практика в модулярной арифметике, позволяющая приводить результаты к корректному диапазону.

Для перевода числа из МСС в ПСС используется КТО. Она позволяет построить число Y в ПСС, исходя из остатков по каждому модулю.

Пример 3. Пусть задано число в МСС в виде остатков A = (23, 87, 12), модули m1 = 49, m2 = 121, m3 = 169.

1) Находим произведение модулей:

M = 49 ∙ 121 ∙ 169 = 1002001.

2) Вычислим: 

3) Используя расширенный алгоритм Евклида, находим обратные элементы:

Найдем обратный элемент X1 для M1 по модулю m1 = 49:

X1 = 46, так как 46 ∙ 20449 ≡ 1 (mod 49).

Найдем обратный элемент X2 для M2 по модулю m2 = 121:

X2 = 16, так как 16 ∙ 8281 ≡ 1 (mod 121).

Найдем обратный элемент X3 для M3 по модулю m3 = 169:

X3 = 157, так как 157 ∙ 5929 ≡ 1 (mod 169).

4) Собираем результат:

Y = (23 ∙ 46 ∙ 20449 + 87 ∙ 16 ∙ 8281 + + 12 ∙ 157 ∙ 5929) (mod 1002001) = 44332430 (mod 1002001) = 244386.

Таким образом, число A = (23, 87, 12) в позиционной системе равно 244386.

На языке программирования Python разработаны программы выполнения рассмотренных операций. Приведены фрагменты алгоритмов и результаты (рис. 1–4).

Исходные данные: в МСС квадратичного диапазона представлены числа A = (23, 87, 12, 34, 56) и B = (17, 34, 157, 89, 112). Модулярные основания m1 = 17, тогда p1 = 172 = 289, m2 = 19, тогда p2 = 19 = 361, m3 = 23, тогда p3 = 232 = 529, m4 = 29, тогда p4 = 292 = 841, m5 = 31, тогда p5 = 312 = 961.

Анализ сложности операций в МСС квадратичного диапазона позволяет оценить ресурсы, необходимые для выполнения операций, и служит важным фактором при выборе подходящей методики и оптимизации производительности [6][8].

Оценка сложности алгоритмов – это мера количества ресурсов времени, необходимого для выполнения алгоритма в зависимости от размера входных данных. Сложность позволяет сравнить алгоритмы и выбрать наиболее эффективный.

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

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

Временная сложность операции сложения: O(n), где n – количество модулей.

В ПСС сложность данных операций напрямую зависит от размера чисел, участвующих в расчетах. Операции занимают время порядка O(n), где n – количество цифр в числе (базисная единица измерения сложности).

Временная сложность операции сложения: O(n), где n – количество модулей.

Для сравнения в позиционной системе счисления (ПСС) сложность следующая:

– классический метод: сложность O(n 2), где n – количество цифр в числе.

– быстрый метод (Карацуба): сложность O(nlog23).

– самый быстрый известный метод (FFT): сложность O(n log n) где n – размер входных данных.

В ПСС при умножении двух чисел длиной n цифр нужно выполнить n 2 операций сложения и переноса, что и приводит к квадратичной сложности.

В МСС квадратичного диапазона же каждое умножение выполняется отдельно по каждому модулю, что существенно снижается до линейной сложности.

В ПСС операция возведения числа в степень имеет следующую сложность.

Простой метод: сложность O(nk), где n – количество цифр, k – показатель степени.

Быстрый метод (Binary Exponentiation): сложность O(n ∙ log k).

В ПСС возведение в степень приводит к росту числа разрядов, что требует больших ресурсов для обработки.

Таблица показывает временную сложность арифметических операций для одинарной и квадратичной, а также позиционной систем счисления. Все они используются для отображения чисел из одинаковых числовых диапазонов. Обозначения в МСС: n – количество модулей, k – показатель степени, M – максимальный модуль; в ПСС: n – размер входных данных (количество цифр в числе), k – показатель степени. 

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

Исследование посвящено анализу модулярной системы счисления квадратичного диапазона, ее структуре и особенностям выполнения основных арифметических операций на серийных (позиционных) компьютерах. Оцениваются временные затраты на выполнение основных арифметических операций в сравнении с позиционными системами счисления. На языке программирования Python разработан алгоритм выполнения основных арифметических операций, приведены результаты его работы.

Проведенное исследование позволяет сделать следующие выводы:

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

К недостаткам реализации МСС квадратичного диапазона на серийном компьютере можно отнести следующие:

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

– большой объем данных – представление чисел в МСС может потребовать больших объемов памяти для хранения промежуточных результатов;

– ограниченные возможности параллельной обработки – серийные компьютеры не приспособлены для параллельной обработки данных, что делает их менее эффективными для массовых вычислений.

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

Альтернативой серийным компьютерам являются специализированные многопроцессорные (модулярные) компьютеры.

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