2

Is it possible to determine if some integer is a fibonacci number in less than N time, where N is the Nth fibonacci number? I'm trying to optimize a solution and this would help tremendously.

I'm trying to exclude all external libraries as well (so things like Math.sqrt() in the answer below will not work for my purposes). Any other suggestions would be great.

Thank you.

Bob John
  • 3,688
  • 14
  • 43
  • 57
  • 2
    The simple iterative approach should be fast enough for any fibonacci number that can be represented with a 32 bit integer (probably even a 64bit integer). On the other hand, the naïve recursive approach is *very* innefficient... which implementation do you have that you want to optimize? – David Rodríguez - dribeas Feb 05 '13 at 22:35
  • What is your solution ? – Alexandre C. Feb 05 '13 at 22:35
  • This question might be better off on the Mathematics site. Have you tried googling for Fibonacci sequence etc.? – occulus Feb 05 '13 at 22:37
  • When you consider that the sqrt from math.h usually translates down to an FPU square root instruction, why don't you want to rely on it? You could also implement a simple algorithm to test if a number is square. int issquare(unsigned int in){ unsigned long long i=in/2; while(i*2>i||i*i>in){i/=2;} while(i*i!=in){ if(i*i>in)return 0; ++i;} return i;} – Kaslai Feb 05 '13 at 22:59
  • If you want to run a few hundred thousand tests for if a number belongs to the fibbonacci sequence though, look for an O(1) solution to checking if a number is a square number. – Kaslai Feb 05 '13 at 23:05
  • Well, how many fibionacci numbers can be represented by your 'integer'? – Roddy Feb 05 '13 at 23:12
  • If he's using 64-bit numbers, only 94... which is why I hope he's dealing with *really* large numbers, because if he isn't, well... http://stackoverflow.com/a/14718501/970543 – Nik Bougalis Feb 05 '13 at 23:22

2 Answers2

6

Perhaps you can use this property:

N is a Fibonacci number if and only if 5 N^2 + 4 or 5N^2 – 4 is a square number.

And look at this post for an efficient solution for the square problem.

Hope this helps

Community
  • 1
  • 1
Baptiste Wicht
  • 7,472
  • 7
  • 45
  • 110
  • I'm trying to exclude external libraries, so things like math.sqrt won't really work for my purposes. Are there any other resources you have in mind? – Bob John Feb 05 '13 at 22:37
  • If you have constraints you should state them in the question to save time. – occulus Feb 05 '13 at 22:39
  • Well that seems like a neat and quick way of checking. You could either write your own sqrt, or since sqrt(N) < N/2 (for x>2) you could just iterate over those numbers? – T. Kiley Feb 05 '13 at 22:44
  • 3
    @BobJohn: Note that in C++, the standard library isn't generally considered "external". Moreover, it's not `math.sqrt()`, it's `std::sqrt()`, found in the `` header. – Robert Mason Feb 05 '13 at 22:45
  • @RobertMason OK, I understand. Then I'll restrict operations to only +,-,/, and *. – Bob John Feb 05 '13 at 22:47
  • +1 for giving the real answer. Check out my answer, though, if you need more whimsy in your diet. – Patrick87 Feb 05 '13 at 22:54
  • Hmm. That 5N^2 term is going to take you outside integer bounds quickly, at which point you'll either need a variable-length math library, or you'll only be able to handle small values of N... – Roddy Feb 05 '13 at 23:09
5

Pre-compute the Fibonacci numbers up to some bound, and then you might be able to search the list for your number more efficiently than by using linear search.

The Fibonacci numbers grow so quickly that I doubt storing them will constitute a problem. I mean, if you're willing to save the first 100 or so, that will cover all numbers up to 3.5e+20.

Say you store the first M Fibonacci numbers. Then the worst-case using binary search is log(M). There are formulae for calculating the Mth Fibonacci number given M; you could use this to approximate M given the Mth Fibonacci number both to get the bound in terms of the number (N, rather than the list size M). I think this makes it end up being something like log(log(N)), but you should check me on that.

Patrick87
  • 27,682
  • 3
  • 38
  • 73
  • 1
    with constexpr you could even precompute everything without having to hardcode the values... – Robert Mason Feb 05 '13 at 22:56
  • 2
    This is actually a great and very usable solution. I don't know why you say it's whimsical in your comment on another answer in this thread. – Nik Bougalis Feb 05 '13 at 23:21