How to find an integer's position in the fibonacci sequence

Question

I'm trying to use fibonacci's sequence as limits for a game's experience points to level conversion (i would like critics on that decision too), something like this:

If a player has 49.450 points, he's in level 25, because the closest smaller fibonacci number is 46.368.

I'm having trouble, however, to figure out how to do that. Apart from creating a map with levels as keys and limits as values, is there any smarter way?

Answer 1

Fibonacci grows exponentially. The base is phi (the golden ratio), so it's not quite as fast as 2^n, but it's still pretty fast. only the smallest 94 or so Fibonacci numbers can be represented by an unsigned 64-bit integer, so a lookup table is probably your best option.

However, if you really did want to compute it, you could invert the closed form solution to get something like:

int fibIndex(long n) {
    return Math.round(Math.log(n * Math.sqrt(5))/Math.log(PHI));
}

this may be of by one, and of course cannot distinguish between the double 1s early in the sequence.