Email this article On the Complexity of Fibonacci Coding
- Authors: Sergeev I.S.1
-
Affiliations:
- Federal State Unitary Enterprise “Kvant Scientific Research Institute,”
- Issue: Vol 54, No 4 (2018)
- Pages: 343-350
- Section: Coding Theory
- URL: https://journal-vniispk.ru/0032-9460/article/view/166557
- DOI: https://doi.org/10.1134/S0032946018040038
- ID: 166557
Cite item
Open Access
Access granted
Subscription Access
Abstract
We show that converting an n-digit number from a binary to Fibonacci representation and backward can be realized by Boolean circuits of complexity O(M(n) log n), where M(n) is the complexity of integer multiplication. For a more general case of r-Fibonacci representations, the obtained complexity estimates are of the form \({2^O}{(\sqrt {\log n} )_n}\).
About the authors
I. S. Sergeev
Federal State Unitary Enterprise “Kvant Scientific Research Institute,”
Author for correspondence.
Email: isserg@gmail.com
Russian Federation, Moscow
Supplementary files
