(43-6) 17 * << * >> * Русский * English * Содержание * Все выпуски

Фибоначчи, трибоначчи, ..., гексаначчи и параллельная безошибочная машинная арифметика

В.М. Чернов1,2

1 ИСОИ РАН – филиал ФНИЦ «Кристаллография и фотоника» РАН,
443001, Россия, г. Самара, ул. Молодогвардейская, д. 151,
2 Самарский национальный исследовательский университет имени академика С.П. Королёва,
443086, Россия, г. Самара, Московское шоссе, д. 34

 PDF, 792 kB

DOI: 10.18287/2412-6179-2019-43-6-1072-1078

Страницы: 1072-1078.

Аннотация:
В работе предлагается новый метод синтеза систем машинной арифметики для «безошибочных» параллельных вычислений. Отличием предлагаемого подхода от вычислений в традиционных системах остаточных классов в прямой сумме модулярных колец является параллелизация вычислений в конечных редукциях неквадратичных глобальных полей, элементы которых представлены в системах счисления порожденными последовательностями степеней корней характеристического полинома для последовательности n-Фибоначчи.

Ключевые слова:
конечные поля, числа n-Фибоначчи и n-Люка, параллельная машинная арифметика.

Цитирование:
Чернов, В.М. Фибоначчи, трибоначчи, ..., гексаначчи и параллельная безошибочная машинная арифметика / В.М. Чернов // Компьютерная оптика. – 2019. – Т. 43, № 6. – С. 1072-1078. – DOI: 10.18287/2412-6179-2019-43-6-1072-1078.

Благодарности:
Работа выполнена при поддержке Министерства науки и высшего образования РФ в рамках выполнения работ по Государственному заданию ФНИЦ «Кристаллография и фотоника» РАН (соглашение № 007-ГЗ/Ч3363/26) в части исследования систем счисления и Российского фонда фундаментальных исследований (проекты РФФИ №19-07-00357 А № 18-29-03135_ мк) в части исследования машинной арифметики.

Литература:
  1. Vasundara, P. Multi-valued logic addition and multiplication in Galois field / P. Vasundara, K.S. Gurumurthy // Proceedings of the 2009 IEEE International Conference on Advances in Computing, Control and Telecommunication Technologies. – 2009. – P. 752-755. – DOI: 10.1109/ACT.2009.190.
  2. Грегори, Р. Безошибочные вычисления. Методы и приложения / Р. Грегори, Е. Кришнамурти; пер. с англ. – М.: Мир, 1988. – 207 с.
  3. Дэвенпорт, Дж. Компьютерная алгебра / Дж. Дэвен­порт, И. Сирэ, Э. Турнье; пер. с англ. – М.: Мир, 1991. – 352 с.
  4. Вариченко, Л.В. Абстрактные алгебраические системы и цифровая обработка сигналов. / Л.В. Вариченко, В.Г. Лабунец, М.А. Раков. – Киев: Наукова думка, 1986. – 247 с.
  5. Нуссбаумер, Г. Быстрое преобразование Фурье и алгоритмы вычисления свёрток / Г.Нуссбаумер; пер. с англ. – М.: Радио и связь, 1985. – 248 с.
  6. Golomb, S.W. Protierties of the sequence 3∙2n+1 / S.W.Golomb // Mathematics and computing. – 1976. –Vol. 30, Issue 135. – P. 657-663.
  7. Alfredson, L.-I. VLSI architectures and arithmetic operations with application to the Fermat number transform / L.-I. Alfredson. – Linkӧping: 1996.
  8. Ananda Mohan, P.V. Residue number systems / P.V. Ananda Mohan. – Switzerland: Springer International Publishing, 2016. – 351 p. – ISBN: 978-3-319-41385-3.
  9. Molahosseini, A.S. Embedded systems design with special arithmetic and number systems / A.S. Molahosseini, L.S. de Sousa, C.-H. Chang. – Springer-Verlag; 2017. – 389 p. – ISBN: 978-3-319-49742-6.
  10. Zeckendorf, E. Representation des nombres naturels par une somme de nombres de Fibonacci ou de nombres de Lucas / E. Zeckendorf // Bulletin de la Societe Royale des Sciences de Liege. – 1972. – Vol. 41. – P. 179-182.
  11. Freitag, H.T. Elements of Zeckendorf arithmetic / H.T. Freitag, G.M. Phillips. – In: Applications of Fibonacci Numbers / ed. by G.E. Bergum, A.N. Philippou, A.F. Ho­radam. –Dordrecht: Springer Science+Business Media, 1998. – P. 129-132.
  12. Fraenkel, A.S. Systems of numeration / A.S. Fraenkel // The American Mathematical Monthly. – 1985. – Vol. 92, Issue 2. – P. 105-114.
  13. Chernov, V.M. Fast algorithm for "error-free" convolution computation using Mersenne-Lucas codes / V.M. Chernov // Chaos, Solitons and Fractals. – 2006. – Vol. 29, Issue 2. – P. 372-380. – DOI: 10.1016/j.chaos.2005.08.081.
  14. Чернов, В.М. Квазипараллельный алгоритм для безошибочного вычисления свёртки в редуцированных кодах Мерсенна–Люка / В.М. Чернов // Компьютерная оптика. – 2015. – Т. 39, № 2. – C. 241-248. – DOI: 10.18287/0134-2452-2015-39-2-241-248.
  15. Чернов, В.М. Системы счисления в модулярных кольцах и их приложения к «безошибочным» вычислениям / В.М. Чернов // Компьютерная оптика. – 2019. – Т. 43, № 5. – С. 901-911. – DOI: 10.18287/2412-6179-2019-43-5-901-911.
  16. Feinberg, M. Fibonacci-Tribonacci / M. Feinberg // The Fibonacci Quarterly. – 1963. – Vol. 1, Issue 30. – P. 71-74.
  17. Flores, I. Direct calculation of k-generalized Fibonacci numbers, Fibonacci Quarterly. – 1976. – Vol. 5. – P. 259-266.
  18. Noe, T.D. Primes in Fibonacci n-step and Lucas n-step sequences / T.D. Noe, J.V. Post // Journal of Integer Sequences. – 2005. – Vol. 8. – 05.4.4.
  19. Гельфонд, А.О. Исчисление конечных разностей. / А.О. Гельфонд. – 4-е изд. – М.: URSS, 2006.
  20. Wimp, J. Computations with recurrence relations / J. Wimp. – Boston, MA: Pitman, 1984.
  21. The on-line encyclopedia of integer sequences® (OEIS®) [Electronical Resource]. – URL: https://oeis.org/ (request date 10.10.2019).
  22. Brown, J.L. Note on complete sequences of integers / J.L. Brown // The American Mathematical Monthly. – 1961. – Vol. 68, Issue 6. – P. 557-560. – DOI: 10.2307/2311150.
  23. Стахов, А.П. Алгоритмическая теория измерения / А.П. Стахов. – М.: Знание, серия Математика и кибернетика, 1979. – Вып. 6.
  24. Стахов, А.П. Коды золотой пропорции / А.П. Стахов // М.: Радио и связь, 1984. – 152 с.
  25. Stakhov, A.P. The mathematics of harmony. From Euclid to contemporary mathematics and computer science / A.P. Stakhov. – World Scientific, 2009.
  26. Чернов, В.М. Арифметические методы синтеза быстрых алгоритмов дискретных ортогональных преобразований / В.М. Чернов. – М.: Физматлит, 2007. – 264 с – ISBN: 5-9221-0940-6.

 

© 2009, IPSI RAS
Россия, 443001, Самара, ул. Молодогвардейская, 151; электронная почта: ko@smr.ru ; тел: +7 (846) 242-41-24 (ответственный секретарь), +7 (846) 332-56-22 (технический редактор), факс: +7 (846) 332-56-20