Lucas number: what changed

Revision 0 to 1. Removed lines have a minus sign; added lines have a plus sign.

Title: Lucas number

New		Line
1	+	The Lucas series is the sequence of numbers:
2	+
3	+	``` pascal
4	+	2, 1, 3, 4, 7, 11, 18, 29, 47, …
5	+	```
6	+
7	+	The idea is, that the next number is produced by summing the two preceding ones.
8	+
9	+	## generation
10	+
11	+	### recursive implementation
12	+
13	+	``` pascal
14	+	type
15	+	/// domain for Lucas number function
16	+	/// where result fits within a nativeUInt
17	+	// You can not name it lucasDomain,
18	+	// since the Lucas number function itself
19	+	// is defined for all whole numbers
20	+	// but the result beyond L(n) exceeds high(nativeUInt).
21	+	lucasLeftInverseRange =
22	+	{$ifdef CPU64} 0..92 {$else} 0..46 {$endif};
23	+
24	+	{**
25	+	calculates Lucas number recursively
26	+
27	+	\param n the index of the Lucas number to calculate
28	+	\return the Lucas number at n,
29	+	unless n is out of range, then 0
30	+	}
31	+	function lucas(const n: lucasLeftInverseRange): nativeUInt;
32	+	begin
33	+	case n of
34	+	// recursive case
35	+	2..high(n):
36	+	begin
37	+	lucas := lucas(n - 2) + lucas(n - 1);
38	+	end;
39	+	// base cases
40	+	1:
41	+	begin
42	+	lucas := 1;
43	+	end;
44	+	0:
45	+	begin
46	+	lucas := 2;
47	+	end;
48	+	// abort case
49	+	otherwise
50	+	begin
51	+	// neutral element of addition
52	+	// indicating n is out of range
53	+	// [there is no n satisfying L(n) = 0]
54	+	lucas := 0;
55	+	end;
56	+	end;
57	+	end;
58	+	```
59	+
60	+	### based on Fibonacci sequence
61	+
62	+	The Lucas numbers can be calculated by using the `fibonacci` function shown in the article [[Fibonacci number]].
63	+
64	+	``` pascal
65	+	{**
66	+	calculates Lucas number based on Fibonacci numbers
67	+
68	+	\param n the index of the Lucas number to calculate
69	+	\return the Lucas number at n,
70	+	unless n is out of range, then 0
71	+	}
72	+	function lucas(const n: lucasLeftInverseRange): nativeUInt;
73	+	begin
74	+	case n of
75	+	1..high(n):
76	+	begin
77	+	lucas := fibonacci(n - 1) + fibonacci(n + 1);
78	+	end;
79	+	0:
80	+	begin
81	+	// We can not deduce L(0) from Fibonacci
82	+	// since that function is not defined for negative n
83	+	// [we would call fibonacci(-1) + fibonacci(1)].
84	+	lucas := 2;
85	+	end;
86	+	otherwise
87	+	begin
88	+	// neutral element of addition
89	+	// indicating n is out of range
90	+	// [there is no n satisfying L(n) = 0]
91	+	lucas := 0;
92	+	end;
93	+	end;
94	+	end;
95	+	```
96	+
97	+	### iterative implementation
98	+
99	+	This is in line with the [[Fibonacci number\|iterative implementation of fibonacci]] but with differing start values. Therefore the code is not repeated here.
100	+
101	+	## lookup
102	+
103	+	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]`.
104	+
105	+	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 [[gmp\|GNU multiple precision arithmetic library]] take this approach.
106	+
107	+	## see also
108	+
109	+	- [Lucas numbers in “the on-line encyclopedia of integer sequences”](https://oeis.org/A000032)
110	+	- [Lucas sequence § “Pascal” on RosettaCode.org](https://rosettacode.org/wiki/Lucas_sequence#Pascal)
111	+	- [[gmp\|GNU multiple precision arithmetic library]]'s functions [`mpz_lucnum_ui` and `mpz_lucnum2_ui`](https://gmplib.org/manual/Lucas-Numbers-Algorithm.html#Lucas-Numbers-Algorithm)
112	+
113	+	---
114	+	From the Free Pascal wiki, page "Lucas number", as it stood on 2022-08-06 after a change by Kai Burghardt, out of the wiki's dump of 2024-05-26. Copyright stays with the author who wrote it, according to the old wiki's [[Licensing]] page. If you have concerns about this material, [message the admin](/wiki-contact).

Back to history