Difference between revisions of "Lucas number"
m (→based on Fibonacci sequence: remove spelling mistake) |
(m) |
||
Line 5: | Line 5: | ||
2, 1, 3, 4, 7, 11, 18, 29, 47, … | 2, 1, 3, 4, 7, 11, 18, 29, 47, … | ||
</syntaxhighlight> | </syntaxhighlight> | ||
− | The idea is, that the next number is produced by summing the two | + | The idea is, that the next number is produced by summing the two preceding ones. |
== generation == | == generation == | ||
The following implementations intends to just show the ''principle''. | The following implementations intends to just show the ''principle''. | ||
− | They lack of input checking, thus | + | They lack of input checking, thus have undefined behavior when supplied with parameters out of range. |
=== recursive implementation === | === recursive implementation === | ||
Line 74: | Line 74: | ||
end; | end; | ||
</syntaxhighlight> | </syntaxhighlight> | ||
+ | |||
+ | === iterative implementation === | ||
+ | This is in line with the [[Fibonacci number#iterative implementation|iterative implementation of <syntaxhighlight lang="pascal" enclose="none">fibonacci</syntaxhighlight>]] but with differing start values. | ||
+ | Therefore the code is not repeated here. | ||
== lookup == | == lookup == | ||
− | Calculating Lucas numbers every time they are needed is time consuming. | + | 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. | 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" enclose="none">fibonacci</syntaxhighlight> table without margin case treatment, it has to be at least expanded to <syntaxhighlight lang="pascal" enclose="none">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. | ||
+ | Also, do not program, what's already programmed. | ||
+ | For instance, the Lucas number functions of the [[gmp|GNU multiple precision arithmetic library]] take this approach. | ||
== see also == | == see also == |
Revision as of 02:56, 9 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 preceding ones.
generation
The following implementations intends to just show the principle. They lack of input checking, thus have undefined 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;
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 programmed. For instance, the Lucas number functions of the GNU multiple precision arithmetic library take this approach.