Difference between revisions of "Lucas number"
m (Reverted edits by Bart (talk) to last revision by Kai Burghardt) |
|||
Line 58: | Line 58: | ||
=== based on Fibonacci sequence === | === based on Fibonacci sequence === | ||
− | The Lucas numbers can be calculated by using the <syntaxhighlight lang="pascal" | + | The Lucas numbers can be calculated by using the <syntaxhighlight lang="pascal" inline>fibonacci</syntaxhighlight> function shown in the article [[Fibonacci number]]. |
<syntaxhighlight lang="pascal" line start="54"> | <syntaxhighlight lang="pascal" line start="54"> | ||
{** | {** | ||
Line 93: | Line 93: | ||
=== iterative implementation === | === iterative implementation === | ||
− | This is in line with the [[Fibonacci number#iterative implementation|iterative implementation of <syntaxhighlight lang="pascal" | + | This is in line with the [[Fibonacci number#iterative implementation|iterative implementation of <syntaxhighlight lang="pascal" inline>fibonacci</syntaxhighlight>]] but with differing start values. |
Therefore the code is not repeated here. | Therefore the code is not repeated here. | ||
Line 100: | Line 100: | ||
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. | 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. | 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. | ||
− | In order to use the <syntaxhighlight lang="pascal" | + | In order to use the <syntaxhighlight lang="pascal" inline>fibonacci</syntaxhighlight> table without margin case treatment, it has to be at least expanded to <syntaxhighlight lang="pascal" inline>fibonacci[-1]</syntaxhighlight>. |
An actual implementation is omitted here, since everyone wants it differently. | An actual implementation is omitted here, since everyone wants it differently. | ||
Line 109: | Line 109: | ||
* [https://oeis.org/A000032 Lucas numbers in “the on-line encyclopedia of integer sequences”] | * [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] | * [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" | + | * [[gmp|GNU multiple precision arithmetic library]]'s functions [https://gmplib.org/manual/Lucas-Numbers-Algorithm.html#Lucas-Numbers-Algorithm <syntaxhighlight lang="c" inline>mpz_lucnum_ui</syntaxhighlight> and <syntaxhighlight lang="c" inline>mpz_lucnum2_ui</syntaxhighlight>] |
Latest revision as of 17:27, 6 August 2022
│
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 preceding ones.
generation
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 unless n is out of range, then 0
19}
20function lucas(const n: lucasLeftInverseRange): nativeUInt;
21begin
22 case n of
23 // recursive case
24 2..high(n):
25 begin
26 lucas := lucas(n - 2) + lucas(n - 1);
27 end;
28 // base cases
29 1:
30 begin
31 lucas := 1;
32 end;
33 0:
34 begin
35 lucas := 2;
36 end;
37 // abort case
38 otherwise
39 begin
40 // neutral element of addition
41 // indicating n is out of range
42 // [there is no n satisfying L(n) = 0]
43 lucas := 0;
44 end;
45 end;
46end;
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 unless n is out of range, then 0
60}
61function lucas(const n: lucasLeftInverseRange): nativeUInt;
62begin
63 case n of
64 1..high(n):
65 begin
66 lucas := fibonacci(n - 1) + fibonacci(n + 1);
67 end;
68 0:
69 begin
70 // We can not deduce L(0) from Fibonacci
71 // since that function is not defined for negative n
72 // [we would call fibonacci(-1) + fibonacci(1)].
73 lucas := 2;
74 end;
75 otherwise
76 begin
77 // neutral element of addition
78 // indicating n is out of range
79 // [there is no n satisfying L(n) = 0]
80 lucas := 0;
81 end;
82 end;
83end;
iterative implementation
This is in line with the iterative implementation of fibonacci
but with differing start values.
Therefore the code is not repeated here.
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.
In order to use the fibonacci
table without margin case treatment, it has to be at least expanded to fibonacci[-1]
.
An actual implementation is omitted here, since everyone wants it differently. Also, do not program, what's already been programmed. For instance, the Lucas number functions of the GNU multiple precision arithmetic library take this approach.