On the Complexity of Fibonacci Coding
Igor' Sergeevich Sergeev · Problems of Information Transmission · 2018
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}$$ .