Chernov V.M. "Exotic" binary number systems for rings of Gauss and Eisenstein integers

 

Samara National Research University, 443086, Russia, Samara, Moskovskoye Shosse 34,

IPSI RAS – Branch of the FSRC “Crystallography and Photonics” RAS, Molodogvardeyskaya 151, 443001, Samara, Russia

 PDF

Abstract:
The paper considers nonstandard binary number systems for rings of Gauss and Eisenstein integers. The principal difference ("exoticism") of such number systems from the canonical number systems introduced by I. Katai for quadratic fields is that as a binary "digital alphabet", it uses a two-element set that does not contain a numeric zero. The paper also synthesizes algorithms for the representation of numbers in the considered number system and characterizes the possibility of an efficient implementation of arithmetic operations.

Keywords:
number systems in quadratic rings, rings of Gauss and Eisenstein integers, machine arithmetic.

Citation:
Chernov VM. "Exotic" binary number systems for rings of Gauss and Eisenstein integers. Computer Optics 2018; 42(6): 1068-1073. DOI: 10.18287/2412-6179-2018-42-6-1068-1073.

References:

  1. Bergman G. A number system with an irrational base. Math Magaz 1957; 31(2): 98-110.
  2. Stahov AP. Golden ratio codes [In Russian]. Moscow: “Radio & Sviaz” Publisher, 1984.
  3. Knuth DE. The art of computer programming. Volume 2: Seminumerical algorithms. 3rd ed. Reading, MA: Addison-Wesley; 1997. ISBN: 978-0-201-89684-8.
  4. Fraenkel AS. Systems of numeration. Amer Math Monthly 1985; 92(2): 105-114. DOI: 10.2307/2322638.
  5. Fraenkel AS. The use and usefulness of numeration systems. Information and Computation 1989; 81(1): 46-61. DOI: 10.1016/0890-5401(89)90028-X.
  6. Joo I, Snitzer F. Expansion with respect to non-integer bases. Graz Math Bericht 1996; 329: 1-35.
  7. Pesavento L, Shapiro S, eds. Fibonacci ratios with pattern recognition. Greenville: Trader Press Inc; 1997. ISBN: 978-0-934380-36-2.
  8. Peters JMH. A ten point FFT claculation which features the golden ratio. The Fibonacci Quarterly 1996; 34(4): 323-325.
  9. Agaian SS, Alaverdian SB. Fast orthogonal Fibonacci transforms. Proc Int Coll on Coding Theory, Osaka, Japan, 1998: 335-352.
  10. Katai I, Szabo J. Canonical number systems in imaginary quadratic fields. Acta Sci Math 1975; 37: 255-260.
  11. Bogdanov PS, Chernov VM. Classification of binary quasi-canonical number systems in imaginary quadratic fields [In Russian]. Computer Optics 2013; 37(3): 391-400.
  12. Thuswardner J. Elementary properties of canonical number systems in quadratic fields. In Book: Bergum GE, Philippou AN, Horadam AF, eds. Applications of Fibonacci numbers. 405-414. Dordrecht: Springer Science+Business Media; 1998: 405-414. DOI: 10.1007/978-94-011-5020-0_45.
  13. BorevichZI, Shafarevich IR. Number theory.New York, London: Academic Press; 1966.
  14. Chernov VM. Ternary number systems in finite fields. Computer Optics 2018; 42(4): 704-711. DOI: 10.18287/2412-6179-2018-42-4-704-711.
  15. Stahov AP. Error-correcting codes (Fibonacci computer) [In Russian]. Moscow: “Znanie” Publisher, 1989. ISBN: 5-07-000867-6.
  16. Chernov VM. The implementation of number-theoretic transforms in the code generated by the redundant number systems [In Russian]. Electronic Simulation 1992; 15(4): 33-37.
  17. Chernov VM, Sobolev DV. Fast algorithms of discrete orthogonal transforms realized in the number system with an irrational base. Optical Memory & Neural Networks 2000; 9(2): 91-100.
  18. Chernov VM, Pershina MV. Fibonacci-Mersenne and Fibonacci-Fermat discrete transforms. Boletim de Informatica, 1999; 9/10: 25-31.
  19. 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.
  20. Chernov VM. Quasi-parallel algorithm for error-free convolution computation using reduced Mersenne–Lucas codes [In Russian]. Computer Optics 2015; 39(2): 241-248. DOI: 10.18287/0134-2452-2015-39-2-241-248.
  21. Chernov V.M Arithmetic methods of fast algorithm of discrete orthogonal transforms synthesis [In Russian]. Moscow: “Fizmathlit” Publisher; 2007. ISBN: 5-9221-0940-6.
© 2009, IPSI RAS
151, Molodogvardeiskaya str., Samara, 443001, Russia; E-mail: journal@computeroptics.ru ; Tel: +7 (846) 242-41-24 (Executive secretary), +7 (846) 332-56-22 (Issuing editor), Fax: +7 (846) 332-56-20