Fibonacci number/fi: what changed

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

Title: Fibonacci number/fi

New		Line
1	+	Fibonaccin lukujono koostuu numeroista:
2	+
3	+	``` pascal
4	+	0, 1, 1, 2, 3, 5, 8, 13, 21, …
5	+	```
6	+
7	+	Ajatuksena on lisätä kaksi viimeistä numeroa yhteen, jolloin saadaan seuraava arvo.
8	+
9	+	## Fibonaccin lukujonon luonti
10	+
11	+	Seuraavat toteutukset osoittavat Fibonacci-numeroiden laskentaperiaatteen. Siinä ei ole syötön valvontaa. Riippuen asetuksista voidaan luoda [[runtime error/fi\|ajonaikainen virhe]] (esim. `{$rangeChecks on}` tai käyttämällä [`system.runError`](https://www.freepascal.org/docs-html/rtl/system=/runerror.html)), [[Raise/fi\|nostaa (raise)]] [[Exceptions/fi\|poikkeus]] tai palauttaa väärä arvo, joka ilmaisee, että jokin meni pieleen.
12	+
13	+	### Rekursiivinen toteutus
14	+
15	+	``` pascal
16	+	type
17	+	/// domain for Fibonacci function
18	+	/// where result is within nativeUInt
19	+	// You can not name it fibonacciDomain,
20	+	// since the Fibonacci function itself
21	+	// is defined for all whole numbers
22	+	// but the result beyond F(n) exceeds high(nativeUInt).
23	+	fibonacciLeftInverseRange =
24	+	{$ifdef CPU64} 0..93 {$else} 0..47 {$endif};
25	+
26	+	{**
27	+	toteuttaa Fibonacci-sekvenssin rekursiivisesti
28	+
29	+	\param n the index of the Fibonacci number to retrieve
30	+	\returns the Fibonacci value at n
31	+	}
32	+	function fibonacci(const n: fibonacciLeftInverseRange): nativeUInt;
33	+	begin
34	+	// optimization: then part gets executed most of the time
35	+	if n > 1 then
36	+	begin
37	+	fibonacci := fibonacci(n - 2) + fibonacci(n - 1);
38	+	end
39	+	else
40	+	begin
41	+	// since the domain is restricted to non-negative integers
42	+	// we can bluntly assign the result to n
43	+	fibonacci := n;
44	+	end;
45	+	end;
46	+	```
47	+
48	+	### Iteratiivinen toteutus
49	+
50	+	Tämä on suositeltavampi sen [[runtime\|ajonaikaisen]] käyttäytymisen suhteen.
51	+
52	+	``` pascal
53	+	{**
54	+	toteuttaa Fibonacci-sekvenssin iteratiivisesti
55	+
56	+	\param n the index of the Fibonacci number to calculate
57	+	\returns the Fibonacci value at n
58	+	}
59	+	function fibonacci(const n: fibonacciLeftInverseRange): nativeUInt;
60	+	type
61	+	/// more meaningful identifiers than simple integers
62	+	relativePosition = (previous, current, next);
63	+	var
64	+	/// temporary iterator variable
65	+	i: longword;
66	+	/// holds preceding fibonacci values
67	+	f: array[relativePosition] of nativeUInt;
68	+	begin
69	+	f[previous] := 0;
70	+	f[current] := 1;
71	+
72	+	// note, in Pascal for-loop-limits are inclusive
73	+	for i := 1 to n do
74	+	begin
75	+	f[next] := f[previous] + f[current];
76	+	f[previous] := f[current];
77	+	f[current] := f[next];
78	+	end;
79	+
80	+	// assign to previous, bc f[current] = f[next] for next iteration
81	+	fibonacci := f[previous];
82	+	end;
83	+	```
84	+
85	+	## Huomioita
86	+
87	+	Fibonacci-numeroa laskettaessa joka kerta uudelleen, kun sitä tarvitaan, tarvitaan jonkin verran muistia ja se vie lisäksi aikaa. [[Application/fi\|Sovellukset]] jotka luottavat voimakkaasti Fibonacci-numeroihin, käyttävät hakutaulukkoa. Sitä ei yleensä enää lasketa, mikä on jo tunnettu tosiasia. Koska Fibonacci-sekvenssi ei muutu, sen laskeminen on lähinnä opetusta, mutta sitä ei ole tarkoitettu tuotanto käyttöön.
88	+
89	+	Se miten se tuotannossa toteutetaan on kuitenkin jätetty pois tästä, koska jokainen tekee sen vähän eri tavalla.
90	+
91	+	## Katso myös
92	+
93	+	- [Fibonacci numbers in the on-line encyclopedia of integer sequences](https://oeis.org/A000045)
94	+	- [Some assembly routine which uses the C calling convention that calculates the nth Fibonacci number](https://freepascal.org/docs-html/current/prog/progsu150.html)
95	+	- [Fibonacci sequence § “Pascal” on RosettaCode.org](https://rosettacode.org/wiki/Fibonacci_sequence#Pascal)
96	+	- [[gmp\|GNU multiple precision arithmetic library]]'s functions [`mpz_fib_ui` and `mpz_fib2_ui`](https://gmplib.org/manual/Fibonacci-Numbers-Algorithm.html#Fibonacci-Numbers-Algorithm)
97	+	- [[Lucas number/fi\|Lucasin luvut]], samantapainen lukusarja mutta erilainen alustus
98	+	- [[Solution 3\|Tao Yue Solution to Fibonacci Sequence Problem]]
99	+
100	+	---
101	+	From the Free Pascal wiki, page "Fibonacci number/fi", 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