Difference between revisions of "Fibonacci number"

From Free Pascal wiki
(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.

see also