Научный журнал
Современные наукоемкие технологии
ISSN 1812-7320
"Перечень" ВАК
ИФ РИНЦ = 0,899

МЕТОД УСКОРЕННОГО УМНОЖЕНИЯ В СИСТЕМЕ ОСТАТОЧНЫХ КЛАССОВ С ИСПОЛЬЗОВАНИЕМ ЛОГАРИФМИЧЕСКИХ ИНТЕРВАЛЬНЫХ ХАРАКТЕРИСТИК

Коржавина А.С. 1 Князьков В.С. 1
1 ФГБОУ ВО «Вятский государственный университет»
Для решения многих задач вычислительной математики, математической физики, экономики, биохимии, криптографии требуется высокая, до 512–1024 бит и более, точность. Операция умножения – одна из наиболее часто выполняемых арифметических операций в таких расчетах. На сегодняшний день основным способом работы с длинными числами являются программные библиотеки позиционной длинной арифметики, главным недостатком которых является резкое снижение быстродействия вследствие возникающих единиц переноса между двоичными разрядами длинного позиционного числа. На практике даже самые быстрые способы умножения дают значительное снижение быстродействия на очень длинных числах, представленных в позиционных системах счисления, поэтому повышение скорости является основной целью при разработке методов умножения. В данной работе рассматривается метод умножения двух длинных чисел с плавающей точкой в гибридном модулярном интервально-логарифмическом формате представления. Мантисса представлена в системе остаточных классов (СОК), которая позволяет заменить последовательные методы выполнения арифметических операций над длинными целыми числами в позиционных системах счисления на параллельные методы выполнения арифметических операций над наборами коротких целых чисел, что существенно ускоряет выполнение операций сложения и умножения. В качестве метаданных формат содержит интервально-логарифмическую характеристику, необходимую для быстрого выполнения операций сравнения и масштабирования. Разработанный метод в среднем приблизительно в 3,4 раза быстрее метода, основанного на позиционной длинной арифметике.
система остаточных классов
умножение
логарифмическая система счисления
интервальная арифметика
формат с плавающей точкой
1. Krougly Z., Davison M., Aiyar S. The Role of High Precision Arithmetic in Calculating Numerical Laplace and Inverse Laplace Transforms. Applied Mathematics. 2017. vol. 8. no. 04. Р. 562–589.
2. Pan B., Wang Y., Tian S. A High-Precision Single Shooting Method for Solving Hypersensitive Optimal Control Problems. Mathematical Problems in Engineering. 2018.
vol. 2018. Р. 1–11.
3. Yang L. et al. solveME: fast and reliable solution of nonlinear ME models. BMC bioinformatics, 2016. vol. 17.
no. 1. Р. 391.
4. Gergidis L.N. et al. Numerical investigation of the acoustic scattering problem from penetrable prolate spheroidal structures using the Vekua transformation and arbitrary precision arithmetic. Mathematical Methods in the Applied Sciences. 2018. Р. 1–16.
5. Asif S., Kong Y. Highly parallel modular multiplier for elliptic curve cryptography in residue number system. Circuits, Systems, and Signal Processing. 2017. vol. 36. no. 3.
Р. 1027–1051.
6. Harvey D., Van Der Hoeven J., Lecerf G. Even faster integer multiplication. Journal of Complexity. 2016. vol. 36. Р. 1–30.
7. G?rard B., Kammerer J.-G., Merkiche N. Contributions to the Design of Residue Number System Architectures. Proceedings of the 22nd IEEE International Symposium on Computer Arithmetic. France. 2015. Р. 105–112.
8. Revol N. Introduction to the IEEE 1788-2015 Standard for Interval Arithmetic. International Workshop on Numerical Software Verification. Springer. Cham. 2017. Р. 14–21.
9. Johansson F. Arb: Efficient arbitrary-precision midpoint-radius interval arithmetic. IEEE Transactions on Computers. 2017. vol. 66 (8). Р. 1281–1292.
10. Коржавина А.С. Исследование эффективности реализации логарифмической интервальной арифметики на универсальных процессорах. Фундаментальные проблемы радиоэлектронного приборостроения. М.: Галлея-Принт. 2016. С. 165–168.
11. Коржавина А.С., Князьков В.С. Методы расширения базиса в системе остаточных классов: обзор и анализ вычислительной сложности // Современные наукоемкие технологии. 2017. № 12. С. 37–42.
12. Lei Y. et al. FPGA implementation of an exact dot product and its application in variable-precision floating-point arithmetic. The Journal of Supercomputing. 2013. vol. 64.
no. 2. Р. 580–605.
13. Князьков В.С., Коржавина А.С. Способ организации выполнения операции умножения двух чисел в модулярно-логарифмическом формате представления с плавающей точкой на гибридных многоядерных процессорах: 2666285 Рос Федерация: G06F7/32; заявл. 06.10.2017; опубл. 06.09.2018 бюл. № 25. 19 с.

Проблема высокоточных вычислений стоит во многих областях вычислительной математики, математической физики, экономики, биохимии. Для решения таких задач, как прямое и обратное преобразования Лапласа [1], оптимальное управление [2], моделирование процессов метаболизма и конфигурации макромолекул [3], волновое рассеяние [4], требуется точность 256–2048 бит. Другой важной областью применения длинной арифметики являются задачи криптографии, в которых операция умножения длинных целых чисел является основной. При этом повышение скорости является основной целью при построении криптосистем, где длина чисел может достигать нескольких тысяч бит [5]. На сегодняшний день основным способом работы с длинными двоичными числами являются программные библиотеки позиционной длинной арифметики, главным недостатком которых является резкое снижение быстродействия вследствие возникающих единиц переноса между двоичными разрядами длинного позиционного числа. Однако даже самые быстрые способы умножения дают значительное снижение быстродействия на очень длинных числах [6]. Альтернативой длинной позиционной арифметики является модулярная арифметика (системы счисления в остаточных классах, СОК).

СОК – это непозиционная система счисления, которая позволяет заменить последовательные методы выполнения арифметических операций над «длинными» целыми числами в позиционных системах счисления на параллельные методы выполнения арифметических операций над наборами «коротких» целых чисел [7]. Главным преимуществом СОК является высокое быстродействие таких операций, как сложение и умножение (так называемые модульные операции), поскольку нет необходимости фиксировать и распространять единицы переноса между разрядами; существенным недостатком – сложность выполнения немодульных операций, таких как операции масштабирования, сравнения и определения переполнения диапазона представления чисел. Учитывая особенности организации вычислений в СОК, их применение наиболее эффективно для решения задач, алгоритмизация которых реализована с существенным преобладанием модульных операций, особенно операций умножения.

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

Гибридный модулярный интервально-логарифмический формат данных

В интервальной арифметике вместо чисел, дискретных точек на числовой оси, используется пара чисел, представляющих собой границы закрытых интервалов, или отрезков числовой оси, что позволяет выполнять расчеты с учетом погрешностей в исходных данных и погрешностей, возникающих в процессе вычислений [8, 9]. При этом все вычисления выполняются таким образом, что результирующий интервал гарантированно содержит точный результат вычислений. В связи с этим интервальная арифметика позволяет повысить достоверность вычислений за счет учета в явном виде влияния ошибок округления [8]. Ширина интервала результата при выполнении арифметических операций в интервальной арифметике является не только критерием точности, но и критерием достоверности, поэтому уменьшение ширины интервала является одной из важных задач. В качестве одного из способов повышения точности интервальной арифметики могут быть применены логарифмические системы счисления (ЛСС) для представления границ интервала [10].

Число в интервально-логарифмическом формате представлено следующим образом:

в качестве одного из способов повышения точности интервала,

kor01.wmf

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

Результат умножения двух чисел, представленных в интервально-логарифмическом формате, определяется следующим образом:

kor02.wmf; kor03.wmf.

Система остаточных классов является непозиционной системой счисления, в которой значения позиционного числа A представлены набором n остатков kor04.wmf от деления числа A на каждый из n модулей kor05.wmf [7] kor06.wmf, где xi вычисляется следующим образом:

kor07.wmf,

где kor08.wmf – целая часть частного kor09.wmf, kor10.wmf – набор оснований или базис СОК.

Произведение kor11.wmf определяет диапазон представления чисел kor12.wmf в СОК, причем, если все числа kor13.wmf являются попарно взаимно простыми, то между любым положительным целым числом A из диапазона [0; P) и числом, представленным в СОК, имеется взаимно однозначное соответствие.

Результат умножения двух чисел kor14.wmf и kor15.wmf, представленных в СОК, определяется следующим образом:

kor16.wmf.

В данной работе предлагается объединить преимущества обоих рассмотренных форматов представления, модулярного и интервально-логарифмического, в новый гибридный модулярный интервально-логарифмический (МИЛ) формат:

kor17.wmf,

где σ – знак числа, kor18.wmf, kor19.wmf – мантисса числа, представленная в СОК, λ – масштаб (порядок) числа, Ll, Lh – интервально-логарифмическая характеристика (ИЛХ) мантиссы числа, kor20.wmf.

Метод выполнения операции умножения в модулярном интервально-логарифмическом формате

Пусть заданы два числа в МИЛ-формате

kor21.wmf

и

kor22.wmf.

Тогда результат

kor23.wmf

будет вычислен следующим образом:

kor24.wmf,

kor25.wmf, kor26.wmf.

Поскольку мантиссы чисел, представленных в МИЛ-формате, ограничены диапазоном [0; P – 1), то при выполнении умножения двух мантисс результат может выйти за пределы диапазона представления kor27.wmf. Для того, чтобы мантисса результата была представима в МИЛ-формате, необходимо выполнить операцию масштабирования kor28.wmf, где kor29.wmf.

Будем выполнять масштабирование обоих операндов до выполнения операции умножения таким образом, чтобы масштабированные сомножители не превышали величину kor30.wmf, то есть

kor31.wmf, kor32.wmf,

где zA и zB – коэффициенты, определяемые соотношениями значений модулей мантисс.

Таким образом, все необходимые вычисления (проверка переполнения, масштабирование) проводятся до непосредственного умножения мантисс.

На основании описанных выше выкладок сформулируем алгоритм умножения двух чисел, представленных в МИЛ-формате.

Шаг 1. Проверка операндов на ноль. Если хотя бы один из операндов равен нулю, то результат равен нулю: σC = 0, λC = 0, kor33.wmf, kor34.wmf, kor35.wmf, иначе перейти к следующему шагу.

Шаг 2. Проверка потери значащих разрядов: если kor36.wmf, где kor37.wmf, то есть результат выполнения операции умножения двух чисел меньше, чем минимально представимое по модулю число, то результат равен нулю: σC = 0, λC = 0, kor38.wmf, kor39.wmf kor40.wmf, иначе перейти к следующему шагу.

Шаг 3. Знак результата: kor41.wmf.

Шаг 4. Проверка переполнения: если kor42.wmf, где kor43.wmf, то есть результат выполнения операции умножения двух чисел выйдет за границы представления чисел в формате IML, то присвоить результату значение «бесконечность»: kor44.wmf, kor45.wmf, kor46.wmf, kor47.wmf, иначе перейти к следующему шагу.

Шаг 5. Проверка переполнения результата умножения модулярных мантисс. В случае, если результат умножения двух модулярных чисел выходит за границы представления, необходимо предварительно уменьшить один их сомножителей или оба сразу путем масштабирования степенью b. Если kor48.wmf, где kor49.wmf, то вычислить значения масштабирующих коэффициентов: kor50.wmf, kor51.wmf, если kor52.wmf и kor53.wmf, то kor54.wmf, kor55.wmf; если kor56.wmf и L < 0, то kor57.wmf, kor58.wmf; если kor59.wmf и kor60.wmf, то kor61.wmf, kor62.wmf; если kor63.wmf и kor64.wmf, то kor65.wmf, kor66.wmf. Если kor67.wmf, то перейти к шагу 7.

Шаг 6. Вычислить значения скорректированных мантисс kor68.wmf и kor69.wmf операндов и скорректировать значение верхней и нижней границы интервальной логарифмической характеристики результата:

kor70.wmf, kor71.wmf.

Скорректировать значения верхней и нижней границ ИЛХ чисел A и B:

kor72.wmf;

kor73.wmf;

kor74.wmf;

kor75.wmf,

где kor76.wmf, если y < x, kor77.wmf, если y > x.

Шаг 7. Выполнить модулярное умножение мантисс: kor78.wmf или kor79.wmf, если мантиссы были скорректированы на шаге 6. Масштаб (порядок) результата: kor80.wmf. ИЛХ результата: kor81.wmf, kor82.wmf.

Оценка быстродействия

Время выполнения предложенного метода (без учета исключений) равно

kor83.wmf,

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

Предположим, что числа из диапазона [0; P) могут появиться с равной вероятностью. Вероятность того, что произведение двух мантисс выйдет за пределы диапазона представления модулярных мантисс, то есть kor84.wmf, равна

kor85.wmf.

Время выполнения операции масштабирования равно [11]:

kor86.wmf,

где tBEX – время выполнения операции расширения базиса, tSUB – время модулярного вычитания, tMUL – время модулярного умножения.

Время расширения базиса при использовании самого быстрого алгоритма равно [11] kor88.wmf.

Таким образом, общее время выполнения разработанного метода не превышает kor89.wmf тактов.

Сравним разработанный метод и метод умножения длинных чисел с плавающей точкой [12], время выполнения которого составляет kor90.wmf тактов, а также с одним из асимптотически быстрых методов умножения, используемых для организации некоторых целочисленных двоичных умножителей (алгоритм Карацубы) [6]. Зависимость времени выполнения метода от разрядности операндов представлена на рисунке.

korg1.wmf

Сравнение быстродействия разработанного метода и методов, основанных на позиционном представлении длинных чисел

Разработанный метод в среднем приблизительно в 3,4 раза быстрее метода, основанного на позиционной длинной арифметике, и в 2,3 раза быстрее одного из асимптотически наиболее быстрых, но в явном виде практически не используемого алгоритма (алгоритм Карацубы) для разрядности мантисс 2048 бит.

Заключение

Разработан метод выполнения операции умножения с использованием модулярного интервально-логарифмического представления чисел с плавающей точкой. Отличительной особенностью представленного метода является использование интервальных логарифмических характеристик для быстрого выполнения немодульных операций сравнения и масштабирования. Разработанный метод в среднем приблизительно в 3,4 раза быстрее метода, основанного на позиционной длинной арифметике, и в 2,3 раза быстрее одного из асимптотически наиболее быстрых, но в явном виде практически не используемого алгоритма (алгоритм Карацубы) для разрядности мантисс 2048 бит.

Сложность разработанного метода выполнения умножения kor91.wmf, что быстрее, чем асимптотически быстрые алгоритмы умножения чисел в позиционной системе счисления: Шёнхаге – Штрассена, имеющего сложность kor92.wmf, и Фюрера со сложностью kor93.wmf.

Представленный метод защищен патентом РФ [13]. В качестве дальнейших направлений исследований предлагается разработка быстрых методов выполнения операций расширения базиса и масштабирования, что позволит уменьшить время выполнения операции умножения чисел в МИЛ-формате.

Исследование выполнено при финансовой поддержке РФФИ в рамках научного проекта № 18-37-00278 мол_а.


Библиографическая ссылка

Коржавина А.С., Князьков В.С. МЕТОД УСКОРЕННОГО УМНОЖЕНИЯ В СИСТЕМЕ ОСТАТОЧНЫХ КЛАССОВ С ИСПОЛЬЗОВАНИЕМ ЛОГАРИФМИЧЕСКИХ ИНТЕРВАЛЬНЫХ ХАРАКТЕРИСТИК // Современные наукоемкие технологии. – 2018. – № 10. – С. 60-64;
URL: https://top-technologies.ru/ru/article/view?id=37195 (дата обращения: 23.10.2021).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074