title: An inverse Fibonacci algorithm?
body: <p>There are dozens of ways of computing F(n) for an arbitrary n, many of which have great runtime and memory usage.</p>
  
  <p>However, suppose I wanted to ask the opposite question:</p>
  
  <blockquote>
    <p>Given F(n) for n > 2, what is n?</p>
  </blockquote>
  
  <p>(The n > 2 restriction is in there since F(1) = F(2) = 1 and there's no unambiguous inverse).</p>
  
  <p>What would be the most efficient way of solving this problem?  It's easy to do this in linear time by enumerating the Fibonacci numbers and stopping when you hit the target number, but is there some way of doing this any faster than that?</p>
  
  <p><strong>EDIT:</strong> currently, the best solution posted here runs in O(log n) time using O(log n) memory, assuming that mathematical operations run in O(1) and that a machine word can hold any number in O(1) space.  I'm curious if it's possible to drop the memory requirements, since you can compute Fibonacci numbers using O(1) space.</p>