Difference between revisions of "Fibonacci number"
(implementation: generation vs. lookup) |
(replace legacy syntaxhighlight syntax; typography; more link) |
||
(9 intermediate revisions by 2 users not shown) | |||
Line 8: | Line 8: | ||
== generation == | == 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 === | === recursive implementation === | ||
− | <syntaxhighlight lang="pascal"> | + | <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 | implements Fibonacci sequence recursively | ||
Line 16: | Line 30: | ||
\returns the Fibonacci value at n | \returns the Fibonacci value at n | ||
} | } | ||
− | function fibonacci(const n: | + | function fibonacci(const n: fibonacciLeftInverseRange): nativeUInt; |
begin | begin | ||
// optimization: then part gets executed most of the time | // optimization: then part gets executed most of the time | ||
Line 33: | Line 47: | ||
=== iterative implementation === | === iterative implementation === | ||
− | This one is preferable for its run-time behavior. | + | This one is preferable for its [[runtime|run-time]] behavior. |
− | <syntaxhighlight lang="pascal"> | + | <syntaxhighlight lang="pascal" line start="13"> |
{** | {** | ||
implements Fibonacci sequence iteratively | implements Fibonacci sequence iteratively | ||
Line 41: | Line 55: | ||
\returns the Fibonacci value at n | \returns the Fibonacci value at n | ||
} | } | ||
− | function fibonacci(const n: | + | function fibonacci(const n: fibonacciLeftInverseRange): nativeUInt; |
type | type | ||
/// more meaningful identifiers than simple integers | /// more meaningful identifiers than simple integers | ||
Line 49: | Line 63: | ||
i: longword; | i: longword; | ||
/// holds preceding fibonacci values | /// holds preceding fibonacci values | ||
− | f: array[relativePosition] of | + | f: array[relativePosition] of nativeUInt; |
begin | begin | ||
f[previous] := 0; | f[previous] := 0; | ||
Line 69: | Line 83: | ||
== lookup == | == lookup == | ||
While calculating the Fibonacci number every time it is needed requires almost no space, it takes a split second of time. | 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. | And yet in general, do not calculate what is already a known fact. | ||
− | Since the Fibonacci sequence | + | 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. | Nevertheless an actual implementation is omitted here, since everyone wants to have it differently, a different flavor. | ||
Line 78: | Line 92: | ||
* [https://oeis.org/A000045 Fibonacci numbers in the on-line encyclopedia of integer sequences] | * [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://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 | + | * [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]] | * [[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
3type
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}
19function fibonacci(const n: fibonacciLeftInverseRange): nativeUInt;
20begin
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;
32end;
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}
19function fibonacci(const n: fibonacciLeftInverseRange): nativeUInt;
20type
21 /// more meaningful identifiers than simple integers
22 relativePosition = (previous, current, next);
23var
24 /// temporary iterator variable
25 i: longword;
26 /// holds preceding fibonacci values
27 f: array[relativePosition] of nativeUInt;
28begin
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];
42end;
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
andmpz_fib2_ui
- Lucas number, a similar series with different initial values
- Tao Yue Solution to Fibonacci Sequence Problem