I just found something cool on accident.

Assuming you start the fibonacci sequence on 2, you can find any of the fibonacci numbers for a given index with a simple trick:

Let Phi = 1.618
Let your index n = n+1

Floor(phi**(n+1+0.328))+1 = the fibonacci number at index n in the sequence.

This probably breaks down past some point but its nifty.

Please describe the process of how you found this by accident. Just curious :D

While this sounds cool, I have lot of questions.

1. Why start at 2 and how does it matter?
2. I don't understand n = n+1
3. Where did 0.328 come from?
4. How did you come up with that equation?
5. Where are we using n=n+1 in the equation?
6. What was the accident?

I did some math where n=10 (10th sequence when starting at 0 and also tried with start at 2), and got following result.

Not sure whether I am inherently dumb at mathematics or just confused with this.

There is a formula for nth Fibonacci number, yours looks different though.

Also, wrongly tagged. You should know better.

@100110111 I hope at least one person found it amusing.

@theabbie just tried it on a few numbers and seemed to work.

@yabbat exploring connections between the fibonacci sequence, other sequences, and logarithms.

@theabbie yeah I vaguely recall something of that nature. Post it if you got it.

I put your formular into spigot, the most exact calculator i know, and it printed completly wrong numbers.
left is the input number, in the middle the result of an pytgon implementation of an fibonacci generator and right the result of your formular in spigot:

as an approximation it works, but it's often off a couple of numbers, and it gets worse the further you go

It gives correct results for a few numbers in the middle though, so if someone needs a quick result for a bunch of fib numbers, and doesn't want to use caching (maybe both space and cycle limitation) it could be servicable as a solution...

also given the weird constants, I'm going to guess that you used machine learning to get this formula.

probably genetic algorithms or something? Or maybe some sort of statistical approach...

@Hazarth if autism counts as machine learning then yes.

Drawing a pentagram on the floor and sacrificing a chicken may or may not also help.

Thanks for the line up of the actual numbers vs the output though, really. That's why I thought it was accurate. Picked some indexes at random and compared. I should have done all indexes up to some n like you did. Had I seen the error I wouldnt have posted it!

Edit:

0.328 was a number that popped out at some point while fiddling with the equation. I'll have to look at the logs to see how I got it.

@Hazarth I also find the pattern of differences between each set of indexes interesting.

Up to 89, the pattern goes 101010...
Etc.

Starting at 6764, the pattern of differences between the indexes of each set becomes..

1, 2, 5, 9, 13, 26, 48.

Just a curiosity of course.

@monkcs
If implementing a fib function ever comes up in one of my interviews I'm gonna use this to blow the interviewer's mind.

You want me to implement Fib(x) so Fib(50) takes less than a minute? How about I do it so Fib(500) takes less than 10 seconds?

@nitnip how long does it normally take?

@Wisecrack I suppose it can vary. My current php configuration started struggling with

foreach (range(1, 40) as $n) echo fib($n).PHP_EOL;

after n=35. It took awhile to get to n=40.

Using the equation above I was able to do the same thing but with range(1,400) almost instantly.

Cool. It's too bad the formula isnt accurate.

But knowing the differences at each index vs the values they are *supposed* to be, might make it cheaper to store the sequence as an index of differences, and then just generate the base values using the formula, and applying the index of differences to get the true fibonacci value for a given index.

@Wisecrack The formula posted by monkcs is exact though.

You just rediscovered Lucas polynomial. These are closely tied to Fibonacci polynomial. These are extensively researched and used in many places. One notable example is William's p+1 integer factorization.

Although your approximation is bad, I still like the thought process. Kudos.

https://en.m.wikipedia.org/wiki/...