0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 (from wiki)

I would code the Fibonacci series as follows.

```
fib(n)
x = -1, y = 1
for n times:
z = x+y
print z
x = y, y = z
```

The issue is that

`x`

is not unsigned and you miss the 32nd bit i.e. I cannot print above 2^31-1.Coming back to the bounds.

fib(n>1) = fib(n-1) + fib(n-2)

fib(n=0) = 0, fib(n=1) = 1

An approximation for the lower bound:

fiblower(n) = 2 * f(n-1)

For n=32, we get 2^32 *f(1).

**Lower bound for n is 32.**

By some observation you can see that for the upper bound:

fibupper(n) = 3/2 * f(n-1)

For n=64 (with little calculation), we get above 2^32.

**Upper bound for n is 64.**

Anyways, the ratio of the Fibonacci numbers tend to the golden ratio Φ (Φ = 1.6180339887...).

i.e. f(n) ~

**Φ*** f(n-1)

[Hat tip to AN]

## No comments:

## Post a Comment