О сложности фибоначчиева кодирования

Показано, что перевод $n$-разрядного числа из двоичного в фибоначчиево представление и обратно может быть реализован булевыми схемами сложности $O(M(n)\log n)$, где $M(n)$ — сложность целочисленного умножения. Для более общего случая $r$-фибоначчиевых представлений полученные оценки сложности имеют вид $2^{O(\sqrt{\log n})}n$.