From positional representation of numbers to positional representation of vectors
DOI:
https://doi.org/10.14311/AP.2023.63.0188Keywords:
number system, positional representation, local function, parallel addition, eventually periodic representationAbstract
To represent real m-dimensional vectors, a positional vector system given by a non-singular matrix M ∈ ℤm×m and a digit set Ɗ ⊂ ℤm is used. If m = 1, the system coincides with the well known numeration system used to represent real numbers. We study some properties of the vector systems which are transformable from the case m = 1 to higher dimensions. We focus on an algorithm for parallel addition and on systems allowing an eventually periodic representation of vectors with rational coordinates.
Downloads
References
A. Cauchy. Sur les moyens d’éviter les erreurs dans les calculs numériques. No. 11 in série I. C.R. Acad. Sc. Paris, France, 1840.
V. Grünwald. Intorno all’aritmetica dei sistemi numerici a base negativa con particolare riguardo al sistema numerico a base negativo-decimale per lo studio delle sue analogie coll’aritmetica ordinaria (decimale). 23. Giornale di matematiche di Battaglini, Italy, 1885.
A. Rényi. Representations for real numbers and their ergodic properties. Acta Mathematica Academiae Scientiarum Hungaricae 8:477–493, 1957. https://doi.org/10.1007/BF02020331
K. Schmidt. On periodic expansions of Pisot numbers and Salem numbers. Bulletin of the London Mathematical Society 12(4):269–278, 1980. https://doi.org/10.1112/blms/12.4.269
T. Vávra, F. Veneziano. Pisot unit generators in number fields. Journal of Symbolic Computation 89:94–108, 2018. https://doi.org/10.1016/j.jsc.2017.11.005
D. E. Knuth. A imaginary number system. Communications of the ACM 3(4):245–247, 1960. https://doi.org/10.1145/367177.367233
W. Penney. A “binary” system for complex numbers. Journal of the ACM 12(2):247–248, 1965. https://doi.org/10.1145/321264.321274
B. Kovács, A. Pethö. Number systems in integral domains, especially in orders of algebraic number fields. Acta Scientiarum Mathematicarum 55:287–299, 1991. http://acta.bibl.u-szeged.hu/15313/1/math_055_fasc_003_004_287-299.pdf.
P. Kirschenhofer, J. Thuswaldner. Shift radix systems: A survey. Numeration and Substitution B46:1–59, 2014. http://hdl.handle.net/2433/226207.
A. Avizienis. Signed-digit numbe representations for fast parallel arithmetic. IRE Transactions on Electronic Computers EC-10(3):389–400, 1961. https://doi.org/10.1109/TEC.1961.5219227
A. Vince. Radix representation and rep-tiling. In Proceedings of the 24-th Southeastern International Conference on Combinatorics, Graph Theory, and Computing, vol. 98, pp. 199–212. 1993.
A. Vince. Replicating tessellations. SIAM Journal on Discrete Mathematics 6(3):501–521, 1993. https://doi.org/10.1137/0406040
A. Kovács. Number expansions in lattices. Mathematical and Computer Modelling 38(7):909–915, 2003. https://doi.org/10.1016/S0895-7177(03)90076-8
J. Jankauskas, J. Thuswaldner. Characterization of rational matrices that admit finite digit representations. Linear Algebra and its Applications 557:350–358, 2018. https://doi.org/10.1016/j.laa.2018.08.006
E. Pelantová, T. Vávra. On positional representation of integer vectors. Linear Algebra and its Applications 633:316–331, 2022. https://doi.org/10.1016/j.laa.2021.10.018
D. Lind, B. Marcus. An Introduction to Symbolic Dynamics and Coding. Cambridge University Press, Cambridge, 1995. https://doi.org/10.1017/CBO9780511626302
C. Frougny, E. Pelantová, M. Svobodová. Parallel addition in non-standard numeration systems. Theoretical Computer Science 412(41):5714–5727, 2011. https://doi.org/10.1016/j.tcs.2011.06.028
S. Akiyama, P. Drungilas, J. Jankauskas. Height reducing problem on algebraic integers. Functiones et Approximatio Commentarii Mathematici 47(1):105–119, 2012. https://doi.org/10.7169/facm/2012.47.1.9
J. Legerský, M. Svobodová. Construction of algorithms for parallel addition in expanding bases via Extending Window Method. Theoretical Computer Science 795:547–569, 2019. https://doi.org/10.1016/j.tcs.2019.08.010
J. Legerský. Minimal non-integer alphabets allowing parallel addition. Acta Polytechnica 58(5):285–291, 2018. https://doi.org/10.14311/AP.2018.58.0285
C. Frougny, E. Pelantová, M. Svobodová. Minimal digit sets for parallel addition in non-standard numeration systems. Journal of Integer Sequencers 16(2):1–36, 2013. https://cs.uwaterloo.ca/journals/JIS/VOL16/Frougny/frougny3.pdf.
T. Vávra. Periodic representations in Salem bases. Israel Journal of Mathematics 242:83–95, 2021. https://doi.org/10.1007/s11856-021-2123-3
E. Isaacson, H. Keller. Analysis of numerical methods. John Wiley & Sons, New York, 1966.
L. Germán, A. Kovács. On number system constructions. Acta Mathematica Hungarica 115:155–167, 2007. https://doi.org/10.1007/s10474-007-5224-5
P. Hudoba, A. Kovács. Toolset for supporting the research of lattice based number expansions. Acta Cybernetica 25(2):271–284, 2021. https://doi.org/10.14232/actacyb.289524
J. Caldwell, K. Hare, T. Vávra. Non-expansive matrix number systems with bases similar to jn(1). [2022-02-01]. arXiv:2110.11937
K. Trivedi, M. Ercegovac. On-line algorithms for division and multiplication. IEEE Transactions on Computers C-26(7):681–687, 1977. https://doi.org/10.1109/TC.1977.1674901
C. Frougny, M. Pavelka, E. Pelantová, M. Svobodová. On-line algorithms for multiplication and division in real and complex numeration systems. Discrete Mathematics & Theoretical Computer Science 21(3), 2019. https://doi.org/10.23638/DMTCS-21-3-14
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2023 Izabella Ingrid Farkas, Edita Pelantová, Milena Svobodová
This work is licensed under a Creative Commons Attribution 4.0 International License.
