Способ определения знака числа в системе остаточных классов
METHOD OF DETERMINING SIGN OF NUMBER IN SYSTEM OF RESIDUAL CLASSES

Изобретение относится к вычислительной технике и предназначено для определения знака числа, представленного в системе остаточных классов.
Известно устройство для определения знаков чисел в системе остаточных классов (патент РФ 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) вычислительной ступени в виде таблицы, где  означает, что берется значение , вычисленное на  вычислительной ступени.
<b>Вычислительная ступень</b>
<b>Операция</b>
<img file="00000108.jpg" he="5" wi="3" img-content="undefined" img-format="jpg" />
<b>17</b>
<b>19</b>
<b>23</b>
<b>31</b>
<img file="00000109.jpg" he="5" wi="3" img-content="undefined" img-format="jpg" />
<b>8</b>
<b>9</b>
<b>11</b>
<b>15</b>
<img file="00000110.jpg" he="5" wi="3" img-content="undefined" img-format="jpg" />
<b>16</b>
<b>18</b>
<b>22</b>
<b>9</b>
1
<img file="00000111.jpg" he="10" wi="20" img-content="undefined" img-format="jpg" />
<img file="00000112.jpg" he="5" wi="7" img-content="undefined" img-format="jpg" />
0
1
3
7
<img file="00000113.jpg" he="6" wi="11" img-content="undefined" img-format="jpg" />
-
9
11
15
<img file="00000114.jpg" he="10" wi="20" img-content="undefined" img-format="jpg" />
<img file="00000115.jpg" he="5" wi="7" img-content="undefined" img-format="jpg" />
0
2
6
24
<img file="00000113.jpg" he="6" wi="11" img-content="undefined" img-format="jpg" />
-
18
22
16
2
<img file="00000116.jpg" he="12" wi="24" img-content="undefined" img-format="jpg" />
<img file="00000117.jpg" he="6" wi="10" img-content="undefined" img-format="jpg" />
-
0
2
6
<img file="00000118.jpg" he="6" wi="11" img-content="undefined" img-format="jpg" />
-
-
11
15
<img file="00000119.jpg" he="12" wi="23" img-content="undefined" img-format="jpg" />
<img file="00000120.jpg" he="6" wi="10" img-content="undefined" img-format="jpg" />
-
0
4
29
<img file="00000118.jpg" he="6" wi="11" img-content="undefined" img-format="jpg" />
-
-
22
26
3
<img file="00000121.jpg" he="12" wi="24" img-content="undefined" img-format="jpg" />
<img file="00000122.jpg" he="6" wi="10" img-content="undefined" img-format="jpg" />
-
-
0
4
<img file="00000123.jpg" he="6" wi="11" img-content="undefined" img-format="jpg" />
-
-
-
<b>15</b>
<img file="00000124.jpg" he="12" wi="23" img-content="undefined" img-format="jpg" />
<img file="00000125.jpg" he="6" wi="10" img-content="undefined" img-format="jpg" />
-
-
0
4
<img file="00000123.jpg" he="6" wi="11" img-content="undefined" img-format="jpg" />
-
-
-
<b>15</b>
После вычисления трех вычислительных ступеней сравним значения  и  с  и . Поскольку , а , то число положительное.
Определить знак числа , найдем вспомогательное значение
Для удобства запишем вычисления (n-1) вычислительной ступени в виде таблицы, где  означает, что берется значение , вычисленное на  вычислительной ступени.
<b>Вычислительная ступень</b>
<b>Операция</b>
<img file="00000108.jpg" he="5" wi="3" img-content="undefined" img-format="jpg" />
<b>17</b>
<b>19</b>
<b>23</b>
<b>31</b>
<img file="00000109.jpg" he="5" wi="3" img-content="undefined" img-format="jpg" />
<b>9</b>
<b>10</b>
<b>12</b>
<b>16</b>
<img file="00000110.jpg" he="5" wi="3" img-content="undefined" img-format="jpg" />
<b>0</b>
<b>0</b>
<b>0</b>
<b>10</b>
1
<img file="00000111.jpg" he="10" wi="20" img-content="undefined" img-format="jpg" />
<img file="00000112.jpg" he="5" wi="7" img-content="undefined" img-format="jpg" />
0
1
3
7
<img file="00000113.jpg" he="6" wi="11" img-content="undefined" img-format="jpg" />
-
9
11
15
<img file="00000114.jpg" he="10" wi="20" img-content="undefined" img-format="jpg" />
<img file="00000115.jpg" he="5" wi="7" img-content="undefined" img-format="jpg" />
0
0
0
10
<img file="00000113.jpg" he="6" wi="11" img-content="undefined" img-format="jpg" />
-
0
0
17
2
<img file="00000116.jpg" he="12" wi="24" img-content="undefined" img-format="jpg" />
<img file="00000117.jpg" he="6" wi="10" img-content="undefined" img-format="jpg" />
-
0
2
6
<img file="00000118.jpg" he="6" wi="11" img-content="undefined" img-format="jpg" />
-
-
11
15
<img file="00000119.jpg" he="12" wi="23" img-content="undefined" img-format="jpg" />
<img file="00000120.jpg" he="6" wi="10" img-content="undefined" img-format="jpg" />
-
0
0
17
<img file="00000118.jpg" he="6" wi="11" img-content="undefined" img-format="jpg" />
-
-
0
27
3
<img file="00000121.jpg" he="12" wi="24" img-content="undefined" img-format="jpg" />
<img file="00000122.jpg" he="6" wi="10" img-content="undefined" img-format="jpg" />
-
-
0
4
<img file="00000123.jpg" he="6" wi="11" img-content="undefined" img-format="jpg" />
-
-
-
<b>15</b>
<img file="00000124.jpg" he="12" wi="23" img-content="undefined" img-format="jpg" />
<img file="00000125.jpg" he="6" wi="10" img-content="undefined" img-format="jpg" />
-
-
0
27
<img file="00000123.jpg" he="6" wi="11" img-content="undefined" img-format="jpg" />
-
-
-
<b>16</b>
После вычисления трех вычислительных ступеней сравним значения  и  с  и . Поскольку , а , то число отрицательное.
Реализация данного способа возможна на программируемых логических интегральных схем (ПЛИС) или с использованием ЭВМ.