Difference between revisions of "Lucas number"

From Lazarus wiki
Jump to navigationJump to search
m
(review)
Line 1: Line 1:
 
{{Lucas_number}}
 
{{Lucas_number}}
  
−
= Lucas number =
+
The Lucas series is the sequence of numbers:
 +
<syntaxhighlight lang="pascal">
 +
2, 1, 3, 4, 7, 11, 18, 29, 47, …
 +
</syntaxhighlight>
 +
The idea is, that the next number is produced by summing the two previous ones.
  
 +
== generation ==
 +
The following implementations intends to just show the ''principle''.
 +
They lack of input checking, thus has uncertain behavior when supplied with parameters out of range.
  
−
The Lucas Sequence is the series of numbers:
+
=== recursive implementation ===
 +
<syntaxhighlight lang="pascal" line start="3">
 +
type
 +
/// domain for Lucas number function
 +
/// where result fits within a nativeUInt
 +
// You can not name it lucasDomain,
 +
// since the Lucas number function itself
 +
// is defined for all whole numbers
 +
// but the result beyond L(n) exceeds high(nativeUInt).
 +
lucasLeftInverseRange =
 +
{$ifdef CPU64} 0..92 {$else} 0..46 {$endif};
  
−
  2, 1, 3, 4, 7, 11, 18, 29, 47, ...
+
{**
 +
calculates Lucas number recursively
 +
   
 +
\param n the index of the Lucas number to calculate
 +
\return the Lucas number at n
 +
}
 +
function lucas(const n: lucasLeftInverseRange): nativeUInt;
 +
begin
 +
case n of
 +
2..high(n):
 +
begin
 +
lucas := lucas(n - 2) + lucas(n - 1);
 +
end;
 +
1:
 +
begin
 +
lucas := 1;
 +
end;
 +
0:
 +
begin
 +
lucas := 2;
 +
end;
 +
otherwise
 +
begin
 +
lucas := 0;
 +
end;
 +
end;
 +
end;
 +
</syntaxhighlight>
  
−
 
+
=== based on Fibonacci sequence ===
−
== Recursive way ==
+
The Lucas numbers can be calculated by using the <syntaxhighlight lang="pascal" enclose="none">fibonacci</syntaxhighlight> function shown in the article [[Fibonacci number]].
−
 
+
<syntaxhighlight lang="pascal" line start="54">
−
<syntaxhighlight>
+
{**
−
 
+
calculates Lucas number based on Fibonacci numbersü
−
function LucasNumber( n : integer ): integer;
+
 +
\param n the index of the Lucas number to calculate
 +
\return the Lucas number at n
 +
}
 +
function lucas(const n: lucasLeftInverseRange): nativeUInt;
 
begin
 
begin
−
  if n > 1 then  
+
if n > 0 then
−
    result := LucasNumber( n - 1 ) + LucasNumber( n - 2 )
+
begin
−
  else
+
lucas := fibonacci(n - 1) + fibonacci(n + 1);
−
    if n = 0 then
+
end
−
      result := 2
+
else
−
    else
+
begin
−
      result := 1;
+
// L(0) := 2
−
end;  
+
lucas := 2;
−
 
+
end;
 +
end;
 
</syntaxhighlight>
 
</syntaxhighlight>
  
−
== Making use of [[Fibonacci number]]s  ==
+
== lookup ==
−
 
+
Calculating Lucas numbers every time they are needed is time consuming.
−
<syntaxhighlight>
+
While the code required for generation takes almost no space, a lookup table is the means of choice when an application needs them a lot.
 +
Since Lucas numbers can be derived from Fibonacci numbers, usually only one table (those with the Fibonacci series) is stored, being a compromise between efficiency and memory utilization.
  
−
function LucasNumber2( n : integer ): integer;
+
An actual implementation is omitted here, since everyone wants it differently.
−
begin
 
−
  result := FibonacciNumber( n + 1 ) + FibonacciNumber( n - 1 );
 
−
end;
 
  
−
</syntaxhighlight>
+
== see also ==
−
<br>
+
* [https://oeis.org/A000032 Lucas numbers in “the on-line encyclopedia of integer sequences”]
 +
* [https://rosettacode.org/wiki/Lucas_sequence#Pascal Lucas sequence § “Pascal” on RosettaCode.org]
 +
* [[gmp|GNU multiple precision arithmetic library]]'s functions [https://gmplib.org/manual/Lucas-Numbers-Algorithm.html#Lucas-Numbers-Algorithm <syntaxhighlight lang="c" enclose="none">mpz_lucnum_ui</syntaxhighlight> and <syntaxhighlight lang="c" enclose="none">mpz_lucnum2_ui</syntaxhighlight>]

Revision as of 23:37, 8 November 2018

│ English (en) │ suomi (fi) │ français (fr) │

The Lucas series is the sequence of numbers: 

2, 1, 3, 4, 7, 11, 18, 29, 47, …

The idea is, that the next number is produced by summing the two previous ones.

generation

The following implementations intends to just show the principle. They lack of input checking, thus has uncertain behavior when supplied with parameters out of range.

recursive implementation

 3type
 4	/// domain for Lucas number function
 5	/// where result fits within a nativeUInt
 6	// You can not name it lucasDomain,
 7	// since the Lucas number function itself
 8	// is defined for all whole numbers
 9	// but the result beyond L(n) exceeds high(nativeUInt).
10	lucasLeftInverseRange =
11		{$ifdef CPU64} 0..92 {$else} 0..46 {$endif};
12
13{**
14	calculates Lucas number recursively
15 
16	\param n the index of the Lucas number to calculate
17	\return the Lucas number at n
18}
19function lucas(const n: lucasLeftInverseRange): nativeUInt;
20begin
21	case n of
22		2..high(n):
23		begin
24			lucas := lucas(n - 2) + lucas(n - 1);
25		end;
26		1:
27		begin
28			lucas := 1;
29		end;
30		0:
31		begin
32			lucas := 2;
33		end;
34		otherwise
35		begin
36			lucas := 0;
37		end;
38	end;
39end;

based on Fibonacci sequence

The Lucas numbers can be calculated by using the fibonacci function shown in the article Fibonacci number. 

54{**
55	calculates Lucas number based on Fibonacci numbersü
56 
57	\param n the index of the Lucas number to calculate
58	\return the Lucas number at n
59}
60function lucas(const n: lucasLeftInverseRange): nativeUInt;
61begin
62	if n > 0 then
63	begin
64		lucas := fibonacci(n - 1) + fibonacci(n + 1);
65	end
66	else
67	begin
68		// L(0) := 2
69		lucas := 2;
70	end;
71end;

lookup

Calculating Lucas numbers every time they are needed is time consuming. While the code required for generation takes almost no space, a lookup table is the means of choice when an application needs them a lot. Since Lucas numbers can be derived from Fibonacci numbers, usually only one table (those with the Fibonacci series) is stored, being a compromise between efficiency and memory utilization.

An actual implementation is omitted here, since everyone wants it differently.

see also

Retrieved from "http://wiki.freepascal.org/index.php?title=Lucas_number&oldid=120967"