# Lucas number/fi

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

Lucasin luvut on numerosarja:

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

Ajatuksena on lisätä kaksi viimeistä numeroa yhteen, jolloin saadaan seuraava arvo.

## Luonti

### Rekursiivinen toteutus

``` 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;
```

### Hyödyntäen Fibonacin sarjaa

Lucas-numerot voidaan laskea käyttämällä `fibonacci` funktiota joka oli esillä Fibonacin luvuissa.

```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;
```

### Iteratiivinen toteutus

Tämä on samanlainen kuin Fibonacin iteratiivisen toteutuksen kanssa, mutta erilaisilla lähtöarvoilla. Siksi koodia ei toisteta tässä.

## Huomioita

Lucas-numeroiden laskeminen aina, kun niitä tarvitaan, on aikaa vievä. Vaikka tarvittava koodi ei vie lähes mitään tilaa, hakutaulukko on valintaväline, kun sovellus tarvitsee niitä usein. Koska Lucas-luvut voidaan saada Fibonacci-numeroista, yleensä vain yksi taulukko (Fibonacci-sarja) on kompromissi tehokkuuden ja muistin käytön välillä. Fibonacci-taulukon käyttämiseksi ilman marginaalikäsittelyä se on ainakin laajennettava fibonaksiin [-1]. Esimerkiksi GNU-monitarkkuuden aritmeettisen kirjaston (GNU multiple precision arithmetic library) Lucas-numerotoiminnot käyttävät tätä lähestymistapaa..