СИСТЕМЫ АНАЛИЗА И ОБРАБОТКИ ДАННЫХ

Модулярная арифметика работает не с самим числом, а с его остатками от деления на некоторые целые числа. В модульной системе счисления, или системе счисления в остаточных классах, многоразрядное целое число в позиционной системе счисления представляется в виде последовательности нескольких позиционных чисел. Эти числа есть остатки (вычеты) от деления исходного числа на некоторые модули, являющиеся взаимно простыми числами. Преимущество модулярного представления состоит в возможности простого распараллеливания выполнения операций сложения, вычитания и умножения.

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

В настоящей статье представлен новый алгоритм восстановления чисел из модульного (модулярного) представления на основе разработанного авторами геометрического подхода на примере систем сравнений с двумя модулями. Показано, что в результате увеличения чисел в позиционном исчислении они последовательно меняются по спирали на поверхности двумерного тора. На основе данного подхода был разработан быстрый алгоритм сравнения чисел и алгоритм для определения переполнения при сложении и умножении чисел в модульном представлении.

Рассмотрение для многомерного случая возможно при анализе многомерного тора и исследовании поведения витков на его поверхности.

1. Бухштаб А.А. Теория чисел. – М.: Просвещение, 1966. – 384 с.

2. Виноградов И.М. Основы теории чисел. – 8-е изд., испр. – М.: Наука, 1972. – 168 с.

3. Галочкин А.И., Нестеренко Ю.В., Шидловский А.Б. Введение в теорию чисел. – 2-е изд. – М.: Изд-во МГУ, 1995. – 159 с.

4. Сизый С.В. Лекции по теории чисел. – М.: Физматлит, 2007. – 190 с.

5. Осипов Н.Н. Теория чисел. – Красноярск: ИКИТ СФУ, 2008. – 117 с.

6. Кнут Д.Э. Искусство программирования. Т. 2. Получисленные алгоритмы. – 3-е изд. – М.: Вильямс, 2007. – 832 с.

7. Gushov V.I., Solodkin Yu.N. Automatic processing of fringe patterns in integer interferometers // Optics and Lasers in Engineering. – 1991. – Vol. 14, iss. 4–5. – P. 311–324.

8. Solution of the problem of phase ambiguity by integer interferometry / V.I. Guzhov, S.P. Il’inykh, R.A. Kuznetsov, A.R. Vagizov // Optoelectronics, Instrumentation and Data Processing. – 2013. – Vol. 49, iss. 2. – P. 178–183.

9. Гужов В.И., Солодкин Ю.Н. Использование свойств целых чисел для расшифровки интерферограмм // Оптика и спектроскопия. – 1988. – Т. 65, № 6. – С. 1123–1128.

10. Measurement system based on multi wavelength interferometry for long gauge block calibration / M. Wengierow, L. Salbut, Z. Ramotowski, R. Szumski, K. Szykiedans // Metrology and Measurement Systems. – 2013. – Vol. 20, iss. 3. – P. 479–490.

11. Zhong J., Zhang Y. Absolute phase-measurement technique based on number theory in multifrequency grating projection profilometry // Applied Optics. – 2001. – Vol. 40, N 4. – P. 492–500.

12. Kujawinska M., Osten W. Fringe pattern analysis methods: up-to-date review // Proceedings SPIE. – 1998. – Vol. 3407. – P. 56–66.

13. Frequency-multiplex Fourier-transform profilometry: a single-shot three-dimensional shape measurement of objects with large height discontinuities and/or surface isolations / M. Takeda, Q. Gu, M. Kinoshita, H. Takai, Y. Takahashi // Applied Optics. – 1997. – Vol. 36, N 22. – P. 5347–5354.

14. Арнольд И.В. Теоретическая арифметика. – М.: Учпедгиз, 1938. – 480 с.

15. Гильберт Д., Кон-Фоссен С. Наглядная геометрия. – М.: Наука, 1981. – 344 с.

16. Гужов В.И., Кабак Е.С., Орлов И.С. Использование модулярной арифметики при фазовых измерениях // Автоматика и программная инженерия. – 2015. – № 1 (1). – С. 97–107.

17. Гужов В.И. Методы измерения 3D профиля объектов. Фазовые методы: учебное пособие. – Новосибирск: Изд-во НГТУ, 2016. – 83 с.