Результат интеллектуальной деятельности: Способ определения знака числа в системе остаточных классов

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

Известно устройство для определения знаков чисел в системе остаточных классов (патент РФ 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) вычислительной ступени в виде таблицы, где означает, что берется значение , вычисленное на вычислительной ступени.

Вычислительная ступень Операция 17 19 23 31 8 9 11 15 16 18 22 9 1 0 1 3 7 - 9 11 15 0 2 6 24 - 18 22 16 2 - 0 2 6 - - 11 15 - 0 4 29 - - 22 26 3 - - 0 4 - - - 15 - - 0 4 - - - 15

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

Определить знак числа , найдем вспомогательное значение

Для удобства запишем вычисления (n-1) вычислительной ступени в виде таблицы, где означает, что берется значение , вычисленное на вычислительной ступени.

Вычислительная ступень Операция 17 19 23 31 9 10 12 16 0 0 0 10 1 0 1 3 7 - 9 11 15 0 0 0 10 - 0 0 17 2 - 0 2 6 - - 11 15 - 0 0 17 - - 0 27 3 - - 0 4 - - - 15 - - 0 27 - - - 16

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

Реализация данного способа возможна на программируемых логических интегральных схем (ПЛИС) или с использованием ЭВМ.