4
$\begingroup$

After writing a program in Java to generate Fibonacci numbers using a recursive algorithm, I noticed the time increase in each iteration is approximately $\Phi$ times greater than the previous.

$\Phi$ is the Golden Ratio, its value is approximately $1.61803398$ and is very closely related to the Fibonacci series.

Here is an output log from the program showing the current iteration number, value, and the time it took to calculate:
30: 832040, calc time: 0.00s, took 1.33333x longer than previous. 31: 1346269, calc time: 0.01s, took 1.50000x longer than previous. 32: 2178309, calc time: 0.01s, took 1.66667x longer than previous. 33: 3524578, calc time: 0.02s, took 1.80000x longer than previous. 34: 5702887, calc time: 0.03s, took 1.55556x longer than previous. 35: 9227465, calc time: 0.05s, took 1.75000x longer than previous. 36: 14930352, calc time: 0.08s, took 1.57143x longer than previous. 37: 24157817, calc time: 0.13s, took 1.66234x longer than previous. 38: 39088169, calc time: 0.21s, took 1.60938x longer than previous. 39: 63245986, calc time: 0.31s, took 1.48544x longer than previous. 40: 102334155, calc time: 0.50s, took 1.63399x longer than previous. 41: 165580141, calc time: 0.80s, took 1.60800x longer than previous. 42: 267914296, calc time: 1.30s, took 1.62065x longer than previous. 43: 433494437, calc time: 2.15s, took 1.65004x longer than previous. 44: 701408733, calc time: 3.47s, took 1.61395x longer than previous. 45: 1134903170, calc time: 5.80s, took 1.67205x longer than previous. 46: 1836311903, calc time: 9.03s, took 1.55619x longer than previous.
I skipped previous values as the time was too short to give a difference.
There definitely does seem to be a relationship between that time and $\Phi$,
I couldn't find any information which explains why this is so.

Here's the algorithm used, it simply gets the previous two values of itself until it gets to the beginning of the series:
function fib(number) { if (number == 0) return 0; if (number == 1) return 1; if (number > 1) return fib(number - 2) + fib(number - 1); }
Is there an explanation why this is happening?

$\endgroup$
3
  • $\begingroup$ en.wikipedia.org/wiki/… $\endgroup$ Commented Feb 2, 2015 at 15:07
  • $\begingroup$ The computation time vs $\phi$ seems like a classical conspiracy theory^^ Note that actual computation time behaves highly chaotic so a small sample with obviously fluctuating times and system loads is insufficient to conclude ;) $\endgroup$ Commented Feb 2, 2015 at 15:16
  • $\begingroup$ BTW There is no if condition needed as last statement for your function. $\endgroup$ Commented Feb 2, 2015 at 15:37

2 Answers 2

Reset to default
1
$\begingroup$

Note that you are not using an optimal algorithm to calculate your Fibonacci numbers. Because it is recursive it calculates all previous numbers again.

Assume $f(n)$ takes time $\approx t_n$ to calculate the number. Then $f(n+1)$ takes time $\approx t_n+t_{n-1}$. This follows the same relationship like the Fibonacci numbers themselves.

Measuring the ratio of time difference is the same like calculating the ratio $$\frac{f(n+1)}{f(n)}$$

and this is know to approach

$$\varphi = \frac{1 + \sqrt{5}}{2} \approx 1.61803\,39887\cdots$$

as $n \to \infty$.

$\endgroup$
1
$\begingroup$

The function nfib that returns the number of calls of fib (which is roughly linear to the time of execution) is following a similiar recursive scheme. You end up with a similiar growth behaviour. See also A001595.

nfib(0) = 1
nfib(1) = 1
nfib(n) = 1 + nfib(n-1) + nfib(n-2)

nfib: 1, 1, 3, 5, 9, 15, 25, 41, 67, ..
 fib: 0, 1, 1, 2, 3,  5,  8, 13, 21, 34, ..

Using

$$ \mathtt{nfib}(n) = 2 \, \mathtt{fib}(n+1) - 1 $$

one sees that $O(\mathtt{nfib}) = O(\mathtt{fib})$.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.