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

Изобретение относится к вычислительной технике. Технический результат заключается в расширении функциональности путем независимости от порядка модулей. Способ определения знака числа в системе остаточных классов, пригодный для реализации средствами вычислительной техники, включает для системы остаточных классов с модулями , , …, и треугольной матрицы с элементами , где , , на основе входного значения числа ), где – остаток от деления числа на модуль , вычисление промежуточных значений вычислительной ступенью, причем я ступень вычисляет выражение для , берут нечетные модули, на основе входного значения ) вычисляют вспомогательное значение где и , каждая я ступень дополнительно вычисляет выражение для , после вычисления значений -й вычислительной ступенью значения и сравнивают соответственно с /2 и /2 и если >/2 или одновременно =/2 и /2, то считают, что исходное число отрицательное, иначе положительное. 2 табл.

 

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

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

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

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

Способ определения знака числа в системе остаточных классов, пригодный для реализации средствами вычислительной техники, включающий для системы остаточных классов с модулями , , …, и треугольной матрицы с элементами , где , , на основе входного значения числа ), где – остаток от деления числа на модуль , вычисление промежуточных значений вычислительной ступенью, причем я ступень вычисляет выражение для , отличающийся тем, что берут нечетные модули, на основе входного значения ) вычисляют вспомогательное значение где и , каждая я ступень дополнительно вычисляет выражение для , после вычисления значений -й вычислительной ступенью значения и сравнивают соответственно с /2 и /2 и если >/2 или одновременно =/2 и /2, то считают, что исходное число отрицательное, иначе положительное.



 

Похожие патенты:

Изобретение относится к арифметическому устройству по модулю семь. Технический результат заключается в обеспечении возможности выполнения нескольких видов арифметических операций по модулю семь.

Изобретение относится к сумматору-умножителю по модулю три. Технический результат заключается в упрощении конструкции устройства.

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

Изобретение относится к нейрокомпьютерной технике и предназначено для классификации классов чисел по заданному модулю р. Техническим результатом является повышение быстродействия нейронной сети при классификации вычетов.

Изобретение относится к нейрокомпьютерной технике и предназначено для классификации классов чисел по заданному модулю р. Техническим результатом является повышение быстродействия нейронной сети при классификации вычетов.

Изобретение относится к области вычислительной техники. Техническим результатом является обеспечение реализации с помощью константной настройки любой из операций (А+В) mod 3, (А-В) mod 3, где А, В ∈ {00,01,10} есть двухразрядные двоичные числа, задаваемые двоичными сигналами.

Изобретение относится к области вычислительной техники. Техническим результатом является обеспечение реализации с помощью константной настройки любой из операций (А+В) mod 3, (А-В) mod 3, где А, В ∈ {00,01,10} есть двухразрядные двоичные числа, задаваемые двоичными сигналами.

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

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

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

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