(43-6) 17 * << * >> * Russian * English * Content * All Issues

Fibonacci, tribonacci, …, hexanacci and parallel “error-free” machine arithmetic

V.M. Chernov1

1 IPSI RAS – Branch of the FSRC “Crystallography and Photonics” RAS,
Molodogvardeyskaya 151, 443001, Samara, Russia,
2 Samara National Research University, 34, Moskovskoye shosse, 443086, Samara, Russia

 PDF, 792 kB

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

Pages: 1072-1078.

Full text of article: Russian language.

Abstract:
The paper proposes a new method of synthesis of machine arithmetic systems for “error-free” parallel computations. The difference of the proposed approach from calculations in traditional Residue Number Systems (RNS) for the direct sum of rings is the parallelization of calculations in finite reductions of non-quadratic global fields whose elements are represented in number systems generated by sequences of powers of roots of the characteristic polynomial for the n-Fibonacci sequence.

Keywords:
finite fields, n-Fibonacci and n-Lucas numbers, parallel machine arithmetic.

Citation:
Chernov VM. Fibonacci,tribonacci, ..., hexanacci and parallel "error-free" machine arithmetic. Computer Optics 2019; 43(6): 1072-1078. DOI: 10.18287/2412-6179-2019-43-6-1072-1078.

Acknowledgements:
The work was partly funded by the Russian Federation Ministry of Science and Higher Education within a state contract with the “Crystallography and Photonics” Research Center of the RAS under agreement 007-ГЗ/Ч3363/26 (“Number systems”) and by Russian Foundation for Basic Research under grants 19-07-00357 А and 18-29-03135_ мк (“Machine arithmetic”).

References:
  1. Vasundara P. Multi-valued logic addition and multiplication in Galois field. Proc IEEE Int Conf Adv Comput Control Telecomm Technol 2009: 752-755. DOI: 10.1109/ACT.2009.190.
  2. Gregory RT, Krishnamurty EV. Method and applications of error-free computation. New York: Springer-Verlag; 1984.
  3. Davenport JH, Siret Y, Tournier E. Computer algebra: Systems and algorithms for algebraic computation. Academic Press; 1988.
  4. Varichenko LV, Labunets VG, Rakov MA. Abstract algebraic systems and digital signal processing [In Russian].Kyiv, “Naukova Dumka” Publisher; 1986.
  5. Nussbaumer HJ. Fast Fourier transform and convolution algorithms. – Berlin, Heidelberg: Springer Verlag; 1982.
  6. Golomb SW. Protierties of the sequence 3∙2n+1. Math Computing 1976; 30(135): 657-663.
  7. Alfredson L-I. VLSI architectures and arithmetic operations with application to the Fermat number transform. Linkӧping: 1996.
  8. Ananda Mohan PV. Residue number systems. Switzerland: Springer International Publishing; 2016. ISBN: 978-3-319-41385-3.
  9. Molahosseini AS, de Sousa LS, Chang C-H, eds. Embedded systems design with special arithmetic and number systems. Springer-Verlag; 2017. 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. Bull Soc Roy Sci Liege 1972; 41: 179-182.
  11. Freitag HT, Phillips GM. Elements of Zeckendorf arithmetic. In Book: Bergum GE, Philippou AN, Horadam AF, eds. Applications of Fibonacci numbers. Dordrecht: Springer Science+Business Media; 1998: 129-132.
  12. Fraenkel AS. Systems of numeration. Amer Math Monthly 1985; 92: 105-114.
  13. Chernov VM. Fast algorithm for "error-free" convolution computation using Mersenne-Lucas codes. Chaos, Solitons and Fractals 2006; 29(2): 372-380. DOI: 10.1016/j.chaos.2005.08.081.
  14. Chernov VM. Quasiparallel algorithm for error-free convolution computation using reduced Mersenne–Lucas codes. Computer Optics 2015; 39(2): 241-248. DOI: 10.18287/0134-2452-2015-39-2-241-248.
  15. Chernov VM. Number systems in modular rings and their applications to "error-free" computations. Computer Optics 2019; 42(5): 901-911. DOI: 10.18287/2412-6179-2019-43-5-901-911.
  16. Feinberg M. Fibonacci-Tribonacci. Fibonacci Quart1963; 1(30): 71-74.
  17. Flores I. Direct calculation of k-generalized Fibonacci numbers, Fibonacci Quart 1967; 5: 259-266.
  18. Noe TD, Post JV. Primes in Fibonacci n-step and Lucas n-step sequences. J Integer Seq 2005; 8: 05.4.4.
  19. Gel’fond AO. Calculus of finite differences [In Russian]. 4-th ed. Мoscow: “URSS” Publisher; 2006.
  20. Wimp J. Computations with recurrence relations. Boston, MA: Pitman; 1984.
  21. The on-line encyclopedia of integer sequences® (OEIS®). Source: <https://oeis.org/>.
  22. Brown JL. Note on complete sequences of integers. Amer Math Monthly 1961; 68(6): 557-560. DOI: 10.2307/2311150.
  23. Stakhov AP. Algorithmic measurement theory [In Russian]. Moscow: “Znanie” Publisher; 1979.
  24. Stakhov AP. Goden ratio codes [In Russian]. Moscow: “Radio i svyas” Publisher; 1984.
  25. Stakhov AP. The mathematics of harmony. From Euclid to contemporary mathematics and computer science. World Scientific; 2009.
  26. Chernov VM. Arithmetic methods for fast algorithms of discrete orthogonal transforms synthesis [In Russian]. Мoscow: “Fizmatlit” Publisher; 2007. ISBN: 5-9221-0940-6.

 

© 2009, IPSI RAS
151, Molodogvardeiskaya str., Samara, 443001, Russia; E-mail: ko@smr.ru ; Tel: +7 (846) 242-41-24 (Executive secretary), +7 (846) 332-56-22 (Issuing editor), Fax: +7 (846) 332-56-20