# Difference between revisions of "Fibonacci number"

(replace legacy syntaxhighlight syntax; typography; more link) |
|||

(12 intermediate revisions by 2 users not shown) | |||

Line 1: | Line 1: | ||

− | {{ | + | {{Fibonacci number}} |

− | |||

− | |||

The Fibonacci Sequence is the series of numbers: | The Fibonacci Sequence is the series of numbers: | ||

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

+ | 0, 1, 1, 2, 3, 5, 8, 13, 21, … | ||

+ | </syntaxhighlight> | ||

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

− | + | == generation == | |

+ | The following implementations show the ''principle'' of how to calculate Fibonacci numbers. | ||

+ | They lack of input checks. | ||

+ | Depending on your preferences you might either want to generate a [[runtime error|run-time error]] (e. g. by [[$rangeChecks|<syntaxhighlight lang="pascal" inline>{$rangeChecks on}</syntaxhighlight>]] or utilizing {{Doc|package=RTL|unit=system=|identifier=runerror|text=<syntaxhighlight lang="pascal" inline>system.runError</syntaxhighlight>}}), [[Raise|raise]] an [[Exceptions|exception]], or simply return a bogus value indicating something went wrong. | ||

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

+ | <syntaxhighlight lang="pascal" line start="3"> | ||

+ | type | ||

+ | /// domain for Fibonacci function | ||

+ | /// where result is within nativeUInt | ||

+ | // You can not name it fibonacciDomain, | ||

+ | // since the Fibonacci function itself | ||

+ | // is defined for all whole numbers | ||

+ | // but the result beyond F(n) exceeds high(nativeUInt). | ||

+ | fibonacciLeftInverseRange = | ||

+ | {$ifdef CPU64} 0..93 {$else} 0..47 {$endif}; | ||

− | + | {** | |

− | + | implements Fibonacci sequence recursively | |

− | + | ||

− | + | \param n the index of the Fibonacci number to retrieve | |

− | function | + | \returns the Fibonacci value at n |

+ | } | ||

+ | function fibonacci(const n: fibonacciLeftInverseRange): nativeUInt; | ||

begin | begin | ||

− | + | // optimization: then part gets executed most of the time | |

− | + | if n > 1 then | |

− | + | begin | |

− | + | fibonacci := fibonacci(n - 2) + fibonacci(n - 1); | |

− | end; | + | end |

− | + | else | |

+ | begin | ||

+ | // since the domain is restricted to non-negative integers | ||

+ | // we can bluntly assign the result to n | ||

+ | fibonacci := n; | ||

+ | end; | ||

+ | end; | ||

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

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

− | This one is preferable. | + | This one is preferable for its [[runtime|run-time]] behavior. |

− | + | <syntaxhighlight lang="pascal" line start="13"> | |

− | <syntaxhighlight> | + | {** |

− | + | implements Fibonacci sequence iteratively | |

− | function | + | |

+ | \param n the index of the Fibonacci number to calculate | ||

+ | \returns the Fibonacci value at n | ||

+ | } | ||

+ | function fibonacci(const n: fibonacciLeftInverseRange): nativeUInt; | ||

+ | type | ||

+ | /// more meaningful identifiers than simple integers | ||

+ | relativePosition = (previous, current, next); | ||

var | var | ||

− | + | /// temporary iterator variable | |

+ | i: longword; | ||

+ | /// holds preceding fibonacci values | ||

+ | f: array[relativePosition] of nativeUInt; | ||

begin | 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; | |

+ | </syntaxhighlight> | ||

− | + | == lookup == | |

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

+ | [[Application]]s 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 == |

+ | * [https://oeis.org/A000045 Fibonacci numbers in the on-line encyclopedia of integer sequences] | ||

+ | * [https://freepascal.org/docs-html/current/prog/progsu150.html Some assembly routine which uses the C calling convention that calculates the nth Fibonacci number] | ||

+ | * [https://rosettacode.org/wiki/Fibonacci_sequence#Pascal Fibonacci sequence § “Pascal” on RosettaCode.org] | ||

+ | * [[gmp|GNU multiple precision arithmetic library]]’s functions [https://gmplib.org/manual/Fibonacci-Numbers-Algorithm.html#Fibonacci-Numbers-Algorithm <syntaxhighlight lang="c" inline>mpz_fib_ui</syntaxhighlight> and <syntaxhighlight lang="c" inline>mpz_fib2_ui</syntaxhighlight>] | ||

+ | * [[Lucas number]], a similar series with different initial values | ||

+ | * [[Solution 3|Tao Yue Solution to Fibonacci Sequence Problem]] |

## Latest revision as of 22:05, 23 October 2019

│
**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

The following implementations show the *principle* of how to calculate Fibonacci numbers.
They lack of input checks.
Depending on your preferences you might either want to generate a run-time error (e. g. by `{$rangeChecks on}`

or utilizing `system.runError`

), raise an exception, or simply return a bogus value indicating something went wrong.

### recursive implementation

```
3 type
4 /// domain for Fibonacci function
5 /// where result is within nativeUInt
6 // You can not name it fibonacciDomain,
7 // since the Fibonacci function itself
8 // is defined for all whole numbers
9 // but the result beyond F(n) exceeds high(nativeUInt).
10 fibonacciLeftInverseRange =
11 {$ifdef CPU64} 0..93 {$else} 0..47 {$endif};
12
13 {**
14 implements Fibonacci sequence recursively
15
16 \param n the index of the Fibonacci number to retrieve
17 \returns the Fibonacci value at n
18 }
19 function fibonacci(const n: fibonacciLeftInverseRange): nativeUInt;
20 begin
21 // optimization: then part gets executed most of the time
22 if n > 1 then
23 begin
24 fibonacci := fibonacci(n - 2) + fibonacci(n - 1);
25 end
26 else
27 begin
28 // since the domain is restricted to non-negative integers
29 // we can bluntly assign the result to n
30 fibonacci := n;
31 end;
32 end;
```

### iterative implementation

This one is preferable for its run-time behavior.

```
13 {**
14 implements Fibonacci sequence iteratively
15
16 \param n the index of the Fibonacci number to calculate
17 \returns the Fibonacci value at n
18 }
19 function fibonacci(const n: fibonacciLeftInverseRange): nativeUInt;
20 type
21 /// more meaningful identifiers than simple integers
22 relativePosition = (previous, current, next);
23 var
24 /// temporary iterator variable
25 i: longword;
26 /// holds preceding fibonacci values
27 f: array[relativePosition] of nativeUInt;
28 begin
29 f[previous] := 0;
30 f[current] := 1;
31
32 // note, in Pascal for-loop-limits are inclusive
33 for i := 1 to n do
34 begin
35 f[next] := f[previous] + f[current];
36 f[previous] := f[current];
37 f[current] := f[next];
38 end;
39
40 // assign to previous, bc f[current] = f[next] for next iteration
41 fibonacci := f[previous];
42 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.

## see also

- Fibonacci numbers in the on-line encyclopedia of integer sequences
- Some assembly routine which uses the C calling convention that calculates the nth Fibonacci number
- Fibonacci sequence § “Pascal” on RosettaCode.org
- GNU multiple precision arithmetic library’s functions
`mpz_fib_ui`

and`mpz_fib2_ui`

- Lucas number, a similar series with different initial values
- Tao Yue Solution to Fibonacci Sequence Problem