On the complexity of Fibonacci coding

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$.