Difference between revisions of "Fibonacci number"

From Free Pascal wiki
(mention mpz_fib_ui; better implementation with sub-ranges)
(see also: insert GMP's algorithm explanation link)
Line 93: Line 93:
 
* [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 § “Pascal” on RosettaCode.org]
 
* [https://rosettacode.org/wiki/Fibonacci_sequence#Pascal Fibonacci sequence § “Pascal” on RosettaCode.org]
* [[gmp|GNU multiple precision arithmetic library]]'s functions <syntaxhighlight lang="c" enclose="none">mpz_fib_ui</syntaxhighlight> and <syntaxhighlight lang="c" enclose="none">mpz_fib2_ui</syntaxhighlight>
+
* [[gmp|GNU multiple precision arithmetic library]]'s functions [https://gmplib.org/manual/Fibonacci-Numbers-Algorithm.html#Fibonacci-Numbers-Algorithm <syntaxhighlight lang="c" enclose="none">mpz_fib_ui</syntaxhighlight> and <syntaxhighlight lang="c" enclose="none">mpz_fib2_ui</syntaxhighlight>]
 
* [[Solution 3|Tao Yue Solution to Fibonacci Sequence Problem]]
 
* [[Solution 3|Tao Yue Solution to Fibonacci Sequence Problem]]
  
 
[[Category:Mathematics]]
 
[[Category:Mathematics]]

Revision as of 21:55, 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

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. 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.

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