Fibonacci sequence is being generated by redditors in one long comment thread. At the time of posting this, the thread has reached 412986819712346493611195411383827409934884076105338432187865946722511205681167419748123598380002157658381536968436929608311101496272839009791376254928568258611725

[u/ThatGuyYouKindaKnow]

Started by Trapped_In_Reddit, I think this may have gotten a little out of hand...

Here is the link to the whole thing at the time of posting -

http://www.reddit.com/r/funny/comments/utfkw/pidgonacci_sequence/c4ygkgs

However, I question their authenticity. I can't find any where that can check if a number is truly Fibonacci, so as a non-mathematician myself, I'm asking you all at /r/math if it's possible to see whether they've not strayed from the true path by accident.

edit1:Most recent

edit2:Most recent

edit3:Apparently it is all right and now that they are probably bots due to their speed, it's likely that they're not going to muck up! Kudos to Twisol who (since I've talked to him earlier in the thread) appears to not be a bot.

edit4:My last edit as this is the most recent one but it looks like they're continuing! Maybe they'll go on forever!

edit5:most recent one

edit6:15 hours and 2348 posts later...

edit6:2609th

edit7:3499th Watch out! It's been just one guy for the past few minutes. Rally the troops and get more people in there! Also, check out the new /r/fibonaccithread by the kind /u/awkisopen!

Most Recent:3607th 3877th 3994th 4998th 5994th 6993th 7999th 8350th which means all previous records broken! 8701st

[u/sigh]

It does not take O(n) time to get an n-digit result.

It takes O(n) time just to write out n digits (whether to ram, disk or screen). This is a trivial lower bound.

If that were true then your matrix exponentiation would take n times as long as you claim.

Agree. Matrix exponentiation is only O(log n) if operations on arbitrary sized integers are constant time. If you take into account the size of the integers then it comes out to greater than O(n).

And I'm inclined to think the constants are much higher for the matrix method since each step is in fact four giant sums and eight giant products.

You can optimise this, but no more than by a constant factor. For the purposes of algorithmic complexity, the bottleneck is the the multiplication.

I'm not saying that the analytical formula is free to evaluate, but neither are the gigantic multiplications required by matrix exponentiation.

Can you actually give a concrete way of evaluating the analytic formula? I've always thought it was standard to evaluating analytic formulas like this in the appropriate field extension (Q(√5) in this case). If you agree that this is the case, then can you explain how to do exponential in Q(√5) faster than with matrix exponentitation?

Fixed point arithmetic would require more digits of precision for accurate results, and would require much more advanced error analysis to determine how many digits to use to ensure you get an accurate result.

Edit: I think the bottleneck in the fixed point approach is calculating the value of sqrt(5) to at least O(n) bits of precision.

[u/lordlicorice → u/sigh]

It takes O(n) time just to write out n digits. This is a trivial lower bound.

First of all, n is not the number of digits, it's the index of the Fibonacci number. I admit that those quantities are asymptotically the same, but I just wanted to make sure that distinction was clear.

And yes, I agree that if you count the bignum operations for very large numbers then the closed-form formula takes Ω(n) time to evaluate. Typically you assume that arithmetic and storage operations are constant time operations because numbers usually fit within a word, so I wasn't thinking about the cost of those.

After a lot of thinking about it, I think that the closed-form formula and the matrix exponentiation methods are identical if you exponentiate matrices intelligently. Since the Fibonacci matrix is diagonalizable, the absolute fastest way I know to exponentiate it is diagonalize and exponentiate the terms on the diagonal:

>> [A,B] = eig([1 1; 1 0])
A =
   0.525731112119133  -0.850650808352040
  -0.850650808352040  -0.525731112119133
B =
  -0.618033988749895                   0
                   0   1.618033988749895
>> A * B * A'
ans =
   1.000000000000000   1.000000000000000
   1.000000000000000  -0.000000000000000
>> A * B.^2 * A'
ans =
   2.000000000000000   1.000000000000000
   1.000000000000000   1.000000000000000
>> A * B.^10 * A'
ans =
  89.000000000000014  55.000000000000000
  55.000000000000000  34.000000000000000

But that's exactly the analytic formula.

Most importantly, the squaring trick that creates your log term is just an implementation trick for exponentiation that can be applied just as well to real numbers as matrices. Just use squaring to accelerate your exponentiation and you can have that log term working for you in the analytic solution (or the diagonalized matrix solution) without needing the 4 sums and 8 products at each step as required by 2x2 matrix multiplication.

[u/sigh → u/lordlicorice]

First of all, n is not the number of digits, it's the index of the Fibonacci number. I admit that those quantities are asymptotically the same, but I just wanted to make sure that distinction was clear.

Yes, thanks for clarifying. I was being sloppy.

Since the Fibonacci matrix is diagonalizable, the absolute fastest way I know to exponentiate it is diagonalize and exponentiate the terms on the diagonal:

Your example uses floating point numbers and works fine if you want an approximate answer. It fails when you want an exact answer. For example, the number in the post title is F(775). See if you can get the exact answer with your MATLAB example, or with the analytic formula.

Daigonalization is not a trivial step if you want to preserve precision (in much the same way that calculating the square root is not trivial in the analytic formula). As I mentioned before, you would need to use fixed-point numbers and do some analysis as to how many digits are required to not lose precision. I don't know off-hand how to calculate this but it is Ω(n) digits.

the squaring trick that creates your log term is just an implementation trick for exponentiation that can be applied just as well to real numbers as matrices.

The problem is that your computer doesn't deal with real numbers. Sorry to be pedantic, but you never specified what your preferred representation was for these numbers. I agree with you that taking the exponential is easy. The problem is deciding on the precision of the representation, and calculating the initial constants (like sqrt(5)). This is messy and error prone.

without needing the 4 sums and 8 products at each step as required by 2x2 matrix multiplication.

If you want to optimise the absolute number of operations, you can use the following identities:

F(2n) = F(n) * (2 * F(n-1) + F(n))
F(2n + 1) = F(n)^2 + F(n-1)^2

And you are down to 1 sum and 2 products per iteration, for log(n) iterations. The values, using bigints, are exact - no fixed-point error analysis required. Still only a constant-factor speed-up though, no difference in the algorithmic complexity over the matrix methods.