Вид РИД
Изобретение
Изобретение относится к вычислительной технике и предназначено для определения знака числа, представленного в системе остаточных классов.
Известно устройство для определения знаков чисел в системе остаточных классов (патент РФ 2557446, опубл. 20.07.2015), содержащее группу входных регистров для хранения числа, представленного в коде симметричной системы остаточных классов, энергонезависимые регистры для хранения интервально-позиционной характеристики константы - наибольшего положительного числа в симметричной системе остаточных классов, блок вычисления интервально-позиционной характеристики, блок проверки правильности интервально-позиционной характеристики, блок сравнения интервально-позиционных характеристик, двухвходовой двоичный дешифратор.
Недостатком данного устройства является использование ресурсоемких операций деления с числами с плавающей точкой, что снижает скорость работы и требует округлений.
Известно устройство для определения знака модулярного числа (патент РФ 2503995, опубл. 10.01.2014), содержащее входные регистры для хранения разрядов исходного числа, блоки умножения, выполненные в виде памяти для хранения произведений и параллельный сумматор.
Недостатком данного устройства является низкая точность, связанная с представлением чисел в формате с плавающей точкой, а именно с ошибками округления.
Наиболее близким к заявляемому изобретению является способ, на котором основано устройство определения знака числа, представленного в системе остаточных классов с модулями , (заявка на изобретение РФ №2020134778, дата подачи 22.10.2020), содержащее
входов остатка, где
– количество модулей
системы остаточных классов,
регистров для хранения разрядов исходного числа,
вычислительную ступень, при этом
-я вычислительная ступень, где
, содержит
сумматоров по модулю
и
блоков умножения на веса
по модулю
, где
и
– мультипликативная инверсия модуля
по модулю
. Старший бит выхода первого блока умножения на веса
по модулю
является выходом знака устройства.
Работа данного устройства основана на следующем математическом аппарате.
В системе остаточных классов (СОК) любое число однозначно представляется набором остатков
от деления числа
на взаимно простые модули СОК
, где
,
- рабочий диапазон СОК,
. Возьмем систему остаточных классов с модулями
. Знак в системе остаточных классов чаще всего вводится разбиением диапазона на две части, тогда с учетом динамического диапазона
в СОК можно представить числа
, если
четное.
Функция определения знака числа, представленного в СОК, определяется следующим образом:
Таким образом можно представить в виде:
(1)
Используя свойство и формулу (1) определение знака сводится двухэтапному алгоритму: первый этап - деление на
, второй этап - деление на
, формально математически определяется следующей формулой
Запишем процесс определения в виде алгоритма:
Алгоритм 1. Определение знака числа
Вход:
– модули СОК
– представление числа
в СОК
- синоптические веса
Выход: – положительное число,
– отрицательное число
1. Для от
до
выполнять:
1.1. Для от
до
выполнять: \\ деление на
1.1.1.
2. Возвратить
На первом этапе вычисляется с помощью
деления на модули СОК
соответственно. На втором этапе вычисляется
.
Недостатком данного способа являются органичные функциональные возможности, связанные с ограничениями, накладываемыми на модули СОК, а именно упорядоченность модулей по возрастанию и представление наибольшего модуля в виде степени 2.
Техническим результатом заявляемого изобретения является расширение функциональности, а именно независимость от порядка модулей.
Данный технический результат достигается тем, что в способе определения знака числа в системе остаточных классов, пригодном для реализации средствами вычислительной техники, включающем для системы остаточных классов с модулями ,
, …,
и треугольной матрицы с элементами
где
,
на основе входного значения числа
), где
– остаток от деления числа
на модуль
, вычисление промежуточных значений
вычислительной ступенью, причем
я ступень вычисляет выражение
для
, берут нечетные модули, на основе входного значения
) вычисляют вспомогательное значение
где
и
, каждая
я ступень дополнительно вычисляет выражение
для
, после вычисления значений
-ой вычислительной ступенью значения
и
сравнивают соответственно с
/2 и
/2 и если
>
/2 или одновременно
=
/2 и
/2, то считают, что исходное число
отрицательное, иначе положительное.
Сущность способа основана на следующем математическом аппарате. Берется СОК с нечетными модулями , тогда функция знака имеет вид
Чтобы определить знак, рассмотрим две функции, и
, где
, тогда функцию знака числа
можно получить из выражения
Рассмотрим пример. Возьмем систему остаточных классов с модулями ,
,
. В данной системе динамический диапазон
и число
будет положительным, если
, т.е.
, а отрицательным для
, т.е.
.
Рассмотрим значения на границе перехода от отрицательных к положительным числам.
Для числа ,
,тогда
Поскольку , а
, то
и число положительное.
Для числа ,
,тогда
Поскольку , а
, то
и число отрицательное.
Запишем функцию определения знака в виде алгоритма для работы с числами, представленными в системе остаточных классов. Данный алгоритм основан на последовательном приближении значения
на основе свойства
.
Алгоритм 2. Определение знака числа
Вход:
– модули СОК,
- нечетные числа
– представление числа
в СОК
- синоптические веса
где
Выход: – положительное число,
– отрицательное число
1. Для от
до
выполнять: \\ выполняется параллельно
1.1.
2. Для от
до
выполнять:
2.1. Для от
до
выполнять:
2.1.1.
2.1.2.
3. Если (() ИЛИ ((
) И (
)) то
3.1. Возвратить 1
4. Иначе
4.1 Возвратить 0
Рассмотрим пример данного способа. Для СОК с нечетными модулями , диапазон СОК
и
.
Синоптические веса равны:
,
,
,
.
Определить знак числа , найдем вспомогательное значение
Для удобства запишем вычисления (n-1) вычислительной ступени в виде таблицы, где означает, что берется значение
, вычисленное на
вычислительной ступени.
|
После вычисления трех вычислительных ступеней сравним значения и
с
и
. Поскольку
, а
, то число положительное.
Определить знак числа , найдем вспомогательное значение
Для удобства запишем вычисления (n-1) вычислительной ступени в виде таблицы, где означает, что берется значение
, вычисленное на
вычислительной ступени.
|
После вычисления трех вычислительных ступеней сравним значения и
с
и
. Поскольку
, а
, то число отрицательное.
Реализация данного способа возможна на программируемых логических интегральных схем (ПЛИС) или с использованием ЭВМ.
Способ определения знака числа в системе остаточных классов, пригодный для реализации средствами вычислительной техники, включающий для системы остаточных классов с модулями , , …, и треугольной матрицы с элементами , где , , на основе входного значения числа ), где – остаток от деления числа на модуль , вычисление промежуточных значений вычислительной ступенью, причем я ступень вычисляет выражение для , отличающийся тем, что берут нечетные модули, на основе входного значения ) вычисляют вспомогательное значение где и , каждая я ступень дополнительно вычисляет выражение для , после вычисления значений -й вычислительной ступенью значения и сравнивают соответственно с /2 и /2 и если >/2 или одновременно =/2 и /2, то считают, что исходное число отрицательное, иначе положительное.