Устройство для сравнения чисел в системе остаточных классов
DEVICE FOR COMPARING NUMBERS IN A SYSTEM OF RESIDUAL CLASSES

Изобретение относится к вычислительной технике и предназначено для выполнения операции сравнения двух чисел, представленных в системе остаточных классов.
Известно устройство для сравнения чисел, представленных в системе остаточных классов, основанное на приближенном методе (А.С. RU №2503992, БИ №1, 10.01.2014), содержащее входные регистры 1, 9 для хранения чисел, схемы определения знаков чисел 2 и 8, схемы сдвига полярности 3, 7, просмотровые таблицы 5, 6 для хранения произведения констант и разрядов СОК, сумматор 10, логический элемент «ИСКЛЮЧАЮЩЕЕ ИЛИ» 4, схемы анализа знака 11. Недостаток устройства - нет возможности проверить корректность получаемого результата сравнения чисел, поскольку не учитываются ошибки округления, образующиеся при вычислении приближенной относительной величины модулярного числа.
Наиболее близким к заявленному изобретению является устройство для сравнения чисел, представленных в системе остаточных классов на основе интервально-позиционных характеристик (А.С. RU №255744, БИ №7, 16.07.2015), содержащее группы входных регистров 1, 2 для хранения сравниваемых модулярных чисел, блоки вычисления интервально-позиционной характеристики 3, 5, блок поразрядного сравнения модулярных чисел 4, блоки проверки правильности интервально-позиционных характеристик 6, 8, блок сравнения интервально-позиционных характеристик 7, схему выдачи результата сравнения 9. Однако данное устройство использует трудоемкие операции в формате с плавающей точкой с направленным округлением.
Техническим результатом заявляемого устройства для сравнения чисел в системе остаточных классов является повышение быстродействия по отношению к другим устройствам на базе приближенных методов. Представленные положения обеспечиваются использованием целочисленной интервальной арифметики, которая реализуется с использованием стандартных двоичных устройств с фиксированной точкой без необходимости выполнения направленных округлений.
Описание устройства: в основе функционирования устройства для сравнения чисел в системе остаточных классов лежит метод целочисленной интервальной оценки относительной величины модулярного числа. Рассмотрим его.
1
2
n
1
2
n
i
i
pi
1
2
n
1
2
n
Пусть базис системы остаточных классов (СОК) задан попарно взаимно простыми модулями p,p, …, p и Р - произведение всех модулей. Тогда целое число X из интервала X∈[О, Р) будет представлено в виде независимых наименьших неотрицательных остатков (вычетов) (х,х, …, x), причем x ≡ X modp ↔ |Х|. Согласно Китайской теореме об остатках (КТО), позиционное значение числа, представленного в СОК остатками 〈х х, …, x〉 по основаниям р, р, …, p, вычисляется по формуле
i
pi
где  - мультипликативная инверсия P по модулю , i∈[1,n],
n - количество модулей.
Согласно теоретико-числовой теореме Эйлера мультипликативную инверсию  , соответствующую сравнению , можно вычислить следующим образом
i
i
i
где ϕ(p) - функция Эйлера, равная количеству целых чисел в диапазоне [1, p], взаимно простых с p.
i
i
1
2
3
4
Пример. Вычислим значения мультипликативных инверсий P по модулям p для системы с основаниями: p= 65535, p = 65534, p = 65533, р = 65531:
Относительная величина Е(Х/Р) модулярного числа Х - это отношение его позиционного значения к произведению модулей Р, то есть
Рассмотрим следующую величину
в которой целая часть определяет коэффициент R, а дробная - значение (X/P).
Поскольку точные рациональные значения величин  а следовательно и (Х/Р), в общем случае не представимы в ЭВМ с ограниченной разрядной сеткой, возникает задача их аппроксимации. Для решения этой задачи представим все величины  в виде интервалов с направленно округленными границами в формате с фиксированной точкой, как показано на фиг. 1. Следовательно, величина (3) также может быть представлена в виде интервала.
i
В случае, если значения всех модулей достаточно большие, величины p могут быть представлены одним интервалом:
i
min
max
i
Обозначим p∈[p; p] - интервальная величина всех модулей p.
Тогда по правилам интервальных вычислений
где ↑ говорит о том, что вычисление выполняется с округлением с избытком («вверх»),
↓ - с недостатком («вниз»).
Величины  и  могут быть вычислены заранее с определенной точностью. Как правило, величина модулей подбирается таким образом, чтобы их двоичным представлением было q-разрядное число, то есть
q-1
q
i
2<p<2.
Тогда обратная величина удовлетворяет условию
В случае, если величина q достаточно велика, то значение величины  в формате с фиксированной точкой будет следующее:
- значение целой части равно 0;
- первые (q - 1) разрядов дробной части равны 0;
- q-й разряд равен 1;
- следующие z разрядов равны нулю;
- следующие (q+z+1)-й, (q+z+2)-й и т.д. разряды определяются непосредственно значением величины  (фиг. 2.).
Таким образом, вместо чисел с плавающей точкой, определяющих значения  и , можно использовать числа с фиксированной точкой - целые числа с масштабирующим коэффициентом.
Величина  усеченная до q+t-1 разрядов после точки равна
,
,
где  - наибольшее целое, не более, чем  - наименьшее целое, не менее, чем t - количество вычисляемых значащих цифр величины
Примем t=z. Тогда величины  и  соответственно будут равны ,  (фиг. 2).
Обозначим
Интервальное число  назовем целочисленной интервальной характеристикой модулярного числа X.
2
Поскольку  - положительные целые числа разрядностью (q+z+logn), где n - количество модулей в базисе, то
q+z
где ⎣ ⎦ обозначает целую часть от деления на 2.
2
x
Иными словами  - старшие log n разрядов чисел   соответственно,  - младшие q+t разрядов чисел .Здесь U - целочисленный аналог относительной величины (Х/Р) модулярного числа X.
В случае, если  то  значения  корректны и могут быть использованы для сравнения модулярных чисел. Если
то необходима дополнительная информация об абсолютной величине числа: если  то  если  то .
Абсолютную погрешность целочисленной интервальной характеристики характеризует ее диаметр
max
min
Пусть разность p - p=α, тогда
Таким образом, верхняя оценка абсолютной погрешности ИПХ не зависит от конкретного модулярного числа и равна
X
t-q
diamW<2⋅α+1.
Объективной мерой точности целочисленной интервальной характеристики является ее относительная ошибка
1
2
n
lt
2
п
lt
2
n
Пусть в СОК с модулями р,р, …, p даны беззнаковые числа А=〈aa,...,а〉 и В=〈bb, -,b〉. Алгоритм их сравнения с использованием целочисленных интервальных характеристик формулируется следующим образом.
i
-1
Шаг 0: предварительно с использованием расширенного алгоритма Евклида вычисляются и сохраняются значения мультипликативных инверсий |P|, i∈G [1,n], n - количество модулей.
Выбираются значения где i ∈ [1,n], n - количество модулей,
- наибольшее целое, не более, чем  - наименьшее целое, не менее, чем
i
i
Шаг 1. Выполняется попарное сравнение остатков для исключения тривиального случая: если a=b для всех i ∈ [1,n], то А=В и алгоритм завершается.
Шаг 2. Вычисляются вектора значений , i∈[1,n].
Шаг 3. Вычисляются значения , i∈[1,n]
Шаг 4. Вычисляются верхние и нижние границы целочисленных интервальных характеристик чисел
2
Выделяются из значений  значения  - старшие log n разрядов чисел  соответственно,  - младшие q+z разрядов чисел  аналогично для второго числа, то есть
Шаг 5. Проверяется первое (необходимое) условие корректного сравнения: если  то переход к шагу 6, иначе - к шагу 7.
Шаг 6. Если  то алгоритм завершается с результатом А<В, если  то алгоритм завершается с результатом А>В. Иначе осуществляется переход к шагу 7.
Шаг 7. Если не выполнены необходимые и достаточные условия для сравнения, то есть не выполнено хотя бы одно из условий  то преобразовать числа А и В из СОК в систему со смешанными основаниями и сравнить цифры полиадических кодов, начиная со старшей, либо сформировать и выдать сигнал о невозможности сравнения чисел. Алгоритм при этом завершается.
Пример 2. Сравнить числа А=〈58765,15597,38429,19957〉 и В=〈18495,11904,64661,20480〉, представленные в СОК с модулями {65535,65534,65533,65531}. Для наглядности будем использовать десятичную, а не двоичную систему счисления, поэтому приведенный алгоритм будет иметь соответствующую десятичную интерпретацию.
0. Определим вначале все необходимые константы для заданной системы модулей:
- набор весов ортогональных базисов: {57343, 21845, 16383, 35496};
- разрядность модулей q=16, разрядность коэффициентов : t=z=13;
- интервальный коэффициент .
1. Числа не равны, поэтому переходим к следующему шагу.
2. Вычислим вектора значений
3. Вычислим значения
A
S=17230+5199+6776+3562=32767;
B
S=113+51210+21945+25026=32763.
4. Вычислим верхние и нижние границы целочисленных интервальных характеристик чисел А и В
A
b
Таким образом, S и S соответствуют нижним границам целочисленных интервальных характеристик, сдвинутым на z разрядов.
Выделяем из значений  значения
5. Выполним сравнение:
следовательно, значения  и  корректны.
следовательно, значения  и  корректны.
6. Сравним  и  268427264>268427259; сравним  и  268460031>268394496.  следовательно, В<А.
Для проверки преобразуем числа в позиционную систему: А=9221825012527697935, B=9220966382894533110, В<А. Таким образом, с использованием целочисленных интервальных характеристик получен правильный результат сравнения двух близлежащих модулярных чисел (числа различаются менее чем на 0,009%).
Выполним проверку корректности вычисления относительной величины модулярных чисел. Вычисления будем производить в десятичной системе счисления. Диапазон представления модулярных чисел Р=18443648025055395869. Вычислим значение Е(А/Р), Е(В/Р) с округлением до десяти цифр после запятой. А/Р ≈ 0,5000000542, В/Р ≈ 0,4999535.
Масштабируем значения  с округлением до десяти цифр после запятой:
следовательно,
Относительная ошибка 0,009%,  Относительная ошибка 0,012%.
Предложенный алгоритм позволил получить высокоточную информацию о величине числа в модулярном представлении без использования трудоемкого преобразования в позиционную систему.
Таким образом, при целочисленной интервальной аппроксимации относительной величины модулярного числа осуществляется естественный учет погрешностей округления, не требующий применения направленных округлений и арифметики с плавающей точкой. Это позволяет простым образом контролировать корректность результата немодульной операции, вне зависимости от числа модулей СОК и их разрядности.
Схема заявляемого устройства для сравнения чисел в системе остаточных классов, функционирующего в соответствии с описанными принципами представлена на фиг.3. Устройство содержит группы входных регистров 1, 2 для хранения сравниваемых модулярных чисел, группы умножителей по модулям на константу 3, 4, параллельные многовходовые двоичные сумматоры 5, 6 для формирования нижних границ целочисленных интервальных характеристик первого и второго чисел соответственно, блок поразрядного сравнения модулярных чисел 7, двоичные сумматоры 8, 9 для формирования верхних границ целочисленных интервальных характеристик первого и второго чисел соответственно, блоки определения корректности вычисления целочисленных интервальных характеристик 10, 13 первого и второго чисел соответственно, блоки сравнения целочисленных интервальных характеристик 11, 12, схему выдачи результата сравнения 14.
Группа входных регистров 1 предназначена для хранения числа А, поступающего по шине данных 15, и содержит регистры 1.1, 1.2, …, 1.n, выходы которых соединены с информационными входами блоков 3.1, 3.2, …, 3.n и 7. В свою очередь, группа входных регистров 2 предназначена для хранения числа В, поступающего по шине данных 16, и содержит регистры 2.1, 2.2, …, 2.n, выходы которых соединены с информационнымип входами блоков 7 и 4.1, 4.2, …, 4.n. Выходы блоков 3.1,3.2, …3.n, 4.1, 4.2,…, 4.n соединены с входами блоков 5, 6 соответственно. Выход блока 7 соединен с одним из входов схемы 14. Выходы блока 5 соединены с входами блока 8, один из выходов блока 5 соединен с одним из входов блока 10, другой выход блока 5 соединен с одним из входов блока 12. Выходы блока 6 соединены с входами блока 9, один из выходов блока 6 соединен с одним из входов блока 11, другой выход блока 6 соединен с одним из входов блока 13. Один из выходов блока 8 соединен с одним из входов блока 10, другой выход блока 8 соединен с одним из входов блока 11. Один из выходов блока 9 соединен с одним из входов блока 13, другой выход блока 9 соединен с одним из входов блока 12. Выход блока 10 соединен с одним из входов схемы 14. Выходы блоков 11, 12 соединены со входами схемы 14. Выход блока 13 соединен с одним из входов схемы 14. Выходы схемы 14 соединены с шинами 17, 18, 19, 20.
1
2
n
1
2
n
i
i
A
B
A
B
A
A
B
B
2
2
2
2
Работа заявляемого устройства для сравнения чисел в системе остаточных классов осуществляется следующим образом. Сравниваемые модулярные числа А=〈а, а, …, a〉 и В=〈b b, …, b〉 поступают по шинам данных 15, 16 и записываются в группы регистров 1, 2 соответственно, откуда подаются на входы блока 7, который производит попарное сравнение остатков (a, b,), i=1, 2, ..., n, и формирует сигнал логической единицы, если все остатки попарно равны, и сигнал логического нуля в противном случае. Одновременно с этим, данные, записанные в группы регистров 1 и 2 соответственно, подаются на входы групп умножителей по модулю на константу 3 и 4 соответственно, далее вычисленные значения подаются на параллельные многовходовые сумматоры 5 и 6 соответственно, где вычисляются смещенные нижние границы целочисленных интервальных характеристик S и Sсоответственно. Вычисленные значения смещенных нижних границ целочисленных интервальных характеристик S и S подаются на входы двоичных сумматоров 8 и 9 соответственно, причем значение S подается на старшие разряды первого входа двоичного сумматора 8 со сдвигом на z разрядов, на младшие z разрядов первого входа двоичного сумматора 8 подается логический ноль, значение S подается на младшие разряды второго входа двоичного сумматора 8, на старшие разряды второго входа двоичного сумматора 8 подается логический ноль, значение S подается на старшие разряды первого входа двоичного сумматора 9 со сдвигом на z разрядов, на младшие z разрядов первого входа двоичного сумматора 9 подается логический ноль, значение S подается на младшие разряды второго входа двоичного сумматора 9, на старшие разряды второго входа двоичного сумматора 9 подается логический ноль. Таким образом вычисляются значения верхних границ целочисленных интервальных характеристик. Старшие log n разрядов параллельного многовходового сумматора 5 и старшие log n разрядов двоичного сумматора 8 подаются на входы блока определения корректности вычисления целочисленных интервальных характеристик 10, при этом, если значения на обоих входах блока 10 равны, то на выходе формируется сигнал логической единицы, иначе - логического ноля. Аналогичным образом работает блок определения корректности вычисления целочисленных интервальных характеристик 13. Старшие log n разрядов параллельного многовходового сумматора 6 и старшие log n разрядов двоичного сумматора 9 подаются на входы блока определения корректности вычисления целочисленных интервальных характеристик 13, при этом, если значения на обоих входах блока 13 равны, то на выходе формируется сигнал логической единицы, иначе - логического ноля. Младшие (z+q) разрядов параллельного многовходового сумматора 5 и младшие (z+q) разрядов двоичного сумматора 8 подаются на входы блока сравнения целочисленных интервальных характеристик 11, при этом, если значение на первом входе блока 11 меньше значения на втором входе блока 11, то на выходе формируется сигнал логической единицы, иначе - логического ноля. Младшие (z+q) разрядов параллельного многовходового сумматора 6 и младшие (z+q) разрядов двоичного сумматора 9 подаются на входы блока сравнения целочисленных интервальных характеристик 12, при этом, если значение на первом входе блока 12 больше значения на втором входе блока 12, то на выходе формируется сигнал логической единицы, иначе - логического ноля. Результаты работы блоков 10, 11, 12, 13 подаются на соответствующие входы схемы выдачи результата сравнения. Работа схемы 14 осуществляется следующим образом: если на входе, соответствующем выходу блока 7, установлена логическая единица, то подается сигнал на шину 17, свидетельствующий о том, что А=В. Иначе анализируются входы, соответствующие выходам блоков 10 и 13: если хотя бы на одном из них установлен логический ноль, то подается сигнал на шину 20, свидетельствующий о том, что результат сравнения чисел А и В не может быть определен в силу недостаточной точности вычисления их целочисленных интервальных характеристик. Иначе анализируются входы, соответствующие выходам блоков 11 и 12: если на входе, соответствующем выходу блока 11 установлена логическая единица, а на входе, соответствующем выходу блока 12, установлен логический ноль, то А<В и подается сигнал на шину 18; если на входе, соответствующем выходу блока 11 установлен логический ноль, а на входе, соответствующем выходу блока 12, установлена логическая единица, то А>В и подается сигнал на шину 19. Иначе подается сигнал на шину 20, свидетельствующий о том, что результат сравнения чисел А и В не может быть определен в силу недостаточной точности вычисления их целочисленных интервальных характеристик.
Пример работы заявляемого устройства для сравнения чисел в системе остаточных классов представлен на фиг. 4. Сравнивались числа А=〈58765,15597,38429,19957〉 и В=〈18495,11904,64661,20480〉, представленные в СОК с модулями {65535,65534,65533,65531}.
2
Трудоемкость заявляемого устройства оценивается следующим образом. Пусть СОК задана n модулями. Тогда для сравнения чисел А и В при условии, что они не равны, требуется выполнить следующие операции: по одной операции модулярного умножения на каждом из n параллельных умножителей по модулю на константу в блоках 3, 4 одновременно; log n операций для вычисления суммы в блоках 5 и 6; по одной операции позиционного сложения в блоках 8, 9 одновременно; по одной операции позиционного сравнения в блоках 10, 11, 12, 13 одновременно. Схема сравнения в блоке 7 позволяет одновременно сравнивать все разряды чисел, причем сравнение производится одновременно с выполнением остальных операций, поэтому время выполнения поразрядного сравнения не учитывается. Схема интерпретации результата 14 построена на базе логических элементов и не требует выполнения дополнительных арифметических операций.
2
2
Таким образом, сравнение двух неравных чисел, представленных в n-модульной СОК, будет выполнено за 2+logn+1+1=logn+3 операций. Для сравнения чисел с помощью устройствана основе вещественных интервальных позиционных характеристик требуется 6n+7 операций. Следовательно, эффект повышения быстродействия от использования заявляемого устройства может достигать в среднем  раз, где n - количество модулей СОК.