 |
С. А. Инютин "Метод вычисления позиционных характеристик модулярного представления с линейной сложностью" |
 |
|
Аннотация.
Разработан метод выбора оснований - модулей для генерации модулярных систем счисления и модулярной арифметики, в которых вычисление позиционной характеристики модулярного представления числовой величины, являющейся нелинейная функцией многих переменных, выполняется с линейной сложностью от количества оснований модулярной системы счисления при вычислении в диапазоне одиночного основания модулярной системы. Это значительно уменьшает разрядность (следовательно, объем аппаратуры) дополнительных блоков модулярного процессора. В исследованиях по модулярной алгоритмике в России и за рубежом отсутствуют методы вычисления позиционных характеристик при таких параметрах. Все немодульные (не распараллеливаемые в модулярной арифметике) операции специализированного процессора с SIMD архитектурой (множество процессорных элементов для потоков данных и единый поток команд) базируются на вычислении позиционных характеристик. Применение метода позволяет выполнять все немодульные операции с минимальной линейной сложностью. Двухэтапный метод содержит выбор оснований модулярной системы счисления и вычисление позиционной характеристики и предназначен для разработчиков специализированных процессоров (сопроцессоров).
Ключевые слова:
модулярная арифметика, модулярная система счисления, модулярные форматы данных, линейная сложность вычисления, позиционная характеристика, нелинейная функция многих переменных.
Стр. 109-122.
DOI 10.14357/20718632240111
EDN AYBEED Литература
1. Акушский И.Я., Юдицкий Д.И. Машинная арифметика в остаточных классах. М.: Советское радио, 1968. 440 с. 2. Амербаев В.М. Теоретические основы машинной арифметики. Алма-Ата: Наука, 1976. 320с. 3. Инютин С.А. Модулярная алгоритмика многоразрядных вычислений. М.: Из-во МАИ, 2020. 160 с. 4. Mandelbaum D. Further Results Decoding Arithmetic Residue Codes. // Transaction on Information Theory, 1998, vol. IT – 24, N 5. -P. 36-41. 5. Амербаев В. М., Стемпковский А.Л., Соловьев Р.А. Принципы рекурсивных модулярных вычислений // Информационные технологии. 2013. № 2. С. 22-27 6. David A. Patterson J., Hennessy L. Computer Organization and Design (Second Edition). London: Morgan Kaufmann Publishers, 2009. 715 p. ISBN 1-55860-428-6. 7. Инютин С.А. Метод вычисления количественной характеристики модулярной величины // Информационные технологии. 2016. Том 22. № 5. С. 343-347. 8. Модулярная арифметика и ее приложения в инфокоммуникационных технологиях. Под редакцией Червякова Н.И. М.: ФизМатЛит, 2016. 395с. 9. Munro I. The Computational Complexity of Algebraic and Numeric Problems (Second edition). New-York: American Elsevier pub. Co; 1986. 174p. ISBN 13: 9780444001566. 10. Инютин С.А. Метод вычисления характеристики отношения порядка для параллельных форматов данных // Информационные технологии. 2017. Том 23. № 8. С. 569-574.
|
