| 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}). |
