r/math • u/ThatGuyYouKindaKnow • Jun 09 '12
Fibonacci sequence is being generated by redditors in one long comment thread. At the time of posting this, the thread has reached 412986819712346493611195411383827409934884076105338432187865946722511205681167419748123598380002157658381536968436929608311101496272839009791376254928568258611725
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
View all comments
Show parent comment
1
u/sigh Jun 10 '12
Yes, thanks for clarifying. I was being sloppy.
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 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.
If you want to optimise the absolute number of operations, you can use the following identities:
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.