A Fibonacci analogue of the two's complement numeration system
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2022
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866929255237025792 |
|---|---|
| author | Labbé, Sébastien Lepšová, Jana |
| author_facet | Labbé, Sébastien Lepšová, Jana |
| contents | Using the classic two's complement notation of signed integers, the fundamental arithmetic operations of addition, subtraction, and multiplication are identical to those for unsigned binary numbers. We introduce a Fibonacci-equivalent of the two's complement notation and we show that addition in this numeration system can be performed by a deterministic finite-state transducer. The result is based on the Berstel adder, which performs addition of the usual Fibonacci representations of nonnegative integers and for which we provide a new constructive proof. Moreover, we characterize the Fibonacci-equivalent of the two's complement notation as an increasing bijection between $\mathbb{Z}$ and a particular language. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2205_02574 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | A Fibonacci analogue of the two's complement numeration system Labbé, Sébastien Lepšová, Jana Formal Languages and Automata Theory Number Theory 68Q45, 11A63, 11B39 Using the classic two's complement notation of signed integers, the fundamental arithmetic operations of addition, subtraction, and multiplication are identical to those for unsigned binary numbers. We introduce a Fibonacci-equivalent of the two's complement notation and we show that addition in this numeration system can be performed by a deterministic finite-state transducer. The result is based on the Berstel adder, which performs addition of the usual Fibonacci representations of nonnegative integers and for which we provide a new constructive proof. Moreover, we characterize the Fibonacci-equivalent of the two's complement notation as an increasing bijection between $\mathbb{Z}$ and a particular language. |
| title | A Fibonacci analogue of the two's complement numeration system |
| topic | Formal Languages and Automata Theory Number Theory 68Q45, 11A63, 11B39 |
| url | https://arxiv.org/abs/2205.02574 |