LOOK-UP TABLE METHOD OF FORWARD BINARY TO RESIDUE NUMBER SYSTEM CONVERSION FOR MODULI {2 F - 1}
Константин Сергеевич Исупов, Vladimir S. Knyazkov · 2012
Проведен анализ классического и табличного методов прямого преобразования двоичных чисел в систему остаточных классов (СОК). Учитывалась временная и ёмкостная сложность параллельных алгоритмов, основанных на исследуемых методах. Выявлены основные недостатки исследуемых методов: классический метод имеет высокую временную сложность ввиду экспоненциальной формы зависимости количества выполняемых операций вычитания от числа оснований (модулей) СОК pi, i = 1, 2, …, n; табличный метод прямого преобразования для оснований произвольного вида требует хранения подстановочных таблиц большого объема, в результате чего они не могут быть размещены в блоках КЭШ памяти первого уровня, а обращение к КЭШ памяти второго и последующего уровней приводит к существенному снижению скорости прямого преобразования. Предложен новый табличный метод преобразования двоичных чисел в систему остаточных классов с основаниями {pi = 2^fi ‒ 1}, отличающийся тем, что в подстановочной таблице хранится не само значение остатка по основанию p i , а номер соответствующего бита унарного кода, который следует установить значением логической единицы для получения значения остатка по основанию p i . Это позволяет ускорить в 2,43 раза выполнение преобразования двоичных чисел в СОК относительно известного табличного метода для оснований произвольного вида, сократив при этом ёмкостную сложность алгоритма (размер подстановочной таблицы) приблизительно в k/]log2k[ раз, где k – разрядность каждого основания pi, а ]log 2 k[ – округленный в большую сторону логарифм log 2 k.