# Difference between revisions of "Fibonacci number"

(blow up) |
(implementation: generation vs. lookup) |
||

Line 7: | Line 7: | ||

The idea is to add the two last numbers in order to produce the next value. | The idea is to add the two last numbers in order to produce the next value. | ||

− | == recursive implementation == | + | == generation == |

+ | === recursive implementation === | ||

<syntaxhighlight lang="pascal"> | <syntaxhighlight lang="pascal"> | ||

{** | {** | ||

Line 31: | Line 32: | ||

</syntaxhighlight> | </syntaxhighlight> | ||

− | == iterative implementation == | + | === iterative implementation === |

This one is preferable for its run-time behavior. | This one is preferable for its run-time behavior. | ||

<syntaxhighlight lang="pascal"> | <syntaxhighlight lang="pascal"> | ||

Line 65: | Line 66: | ||

end; | end; | ||

</syntaxhighlight> | </syntaxhighlight> | ||

+ | |||

+ | == lookup == | ||

+ | While calculating the Fibonacci number every time it is needed requires almost no space, it takes a split second of time. | ||

+ | Applications heavily relying on Fibonacci numbers definitely want to use a lookup table instead. | ||

+ | And yet in general, do not calculate what is already a known fact. | ||

+ | Since the Fibonacci sequence doesn't change, actually calculating it is a textbook demonstration but not intended for production use. | ||

+ | |||

+ | Nevertheless an actual implementation is omitted here, since everyone wants to have it differently, a different flavor. | ||

== see also == | == see also == |

## Revision as of 14:40, 8 November 2018

│
**Deutsch (de)** │
**English (en)** │
**suomi (fi)** │
**français (fr)** │
**русский (ru)** │

The Fibonacci Sequence is the series of numbers:

```
0, 1, 1, 2, 3, 5, 8, 13, 21, …
```

The idea is to add the two last numbers in order to produce the next value.

## generation

### recursive implementation

```
{**
implements Fibonacci sequence recursively
\param n the index of the Fibonacci number to retrieve
\returns the Fibonacci value at n
}
function fibonacci(const n: byte): qword;
begin
// optimization: then part gets executed most of the time
if n > 1 then
begin
fibonacci := fibonacci(n - 2) + fibonacci(n - 1);
end
else
begin
// since the domain is restricted to non-negative integers
// we can bluntly assign the result to n
fibonacci := n;
end;
end;
```

### iterative implementation

This one is preferable for its run-time behavior.

```
{**
implements Fibonacci sequence iteratively
\param n the index of the Fibonacci number to calculate
\returns the Fibonacci value at n
}
function fibonacci(const n: longword): qword;
type
/// more meaningful identifiers than simple integers
relativePosition = (previous, current, next);
var
/// temporary iterator variable
i: longword;
/// holds preceding fibonacci values
f: array[relativePosition] of qword;
begin
f[previous] := 0;
f[current] := 1;
// note, in Pascal for-loop-limits are inclusive
for i := 1 to n do
begin
f[next] := f[previous] + f[current];
f[previous] := f[current];
f[current] := f[next];
end;
// assign to previous, bc f[current] = f[next] for next iteration
fibonacci := f[previous];
end;
```

## lookup

While calculating the Fibonacci number every time it is needed requires almost no space, it takes a split second of time. Applications heavily relying on Fibonacci numbers definitely want to use a lookup table instead. And yet in general, do not calculate what is already a known fact. Since the Fibonacci sequence doesn't change, actually calculating it is a textbook demonstration but not intended for production use.

Nevertheless an actual implementation is omitted here, since everyone wants to have it differently, a different flavor.