diplomsko delo
Povzetek
V diplomski nalogi so predstavljeni in analizirani načini algoritmičnega izračuna Fibonaccijevih števil. V prvem delu je predstavljeno teoretično ozadje
računanja elementov Fibonaccijevega zaporedja in aritmetika v poljubni natančnosti,
ki nam omogoča operiranje s števili, ki velikostno presegajo dolžino
procesorskih registrov. Opisani so algoritmi, ki temeljijo na osnovni rekurzivni
zvezi Fibonaccijevega zaporedja, matrični algoritmi, algoritmi na podlagi
Binetove formule in algoritem, ki pri izračunu uporablja binomske koeficiente.
V drugem delu so predstavljeni rezultati eksperimentalne primerjave
predstavljenih algoritmov, ki smo jih implementirali v programskem jeziku C,
za izvajanje aritmetike v poljubni natančnosti pa je bila uporabljena knjižnica
GNU MP.
Ključne besede
Fibonaccijeva števila;aritmetika poljubne natančnosti;časovna zahtevnost;rekurzija;univerzitetni študij;diplomske naloge;
Podatki
Jezik: |
Slovenski jezik |
Leto izida: |
2022 |
Tipologija: |
2.11 - Diplomsko delo |
Organizacija: |
UL FRI - Fakulteta za računalništvo in informatiko |
Založnik: |
[G. Močnik] |
UDK: |
004:51(043.2) |
COBISS: |
97925635
|
Št. ogledov: |
164 |
Št. prenosov: |
39 |
Ocena: |
0 (0 glasov) |
Metapodatki: |
|
Ostali podatki
Sekundarni jezik: |
Angleški jezik |
Sekundarni naslov: |
Comparison of algorithms for computing Fibonacci numbers |
Sekundarni povzetek: |
In this thesis, we present and analyse ways of algorithmically computing
Fibonacci numbers. In the first part we describe theoretical background
of computing elements of the Fibonacci sequence. We also describe arbitrary
precision arithmetic that allows us to do mathematical operations on
numbers that are larger than the length of processor registers. We describe
algorithms that are based on the Fibonacci sequence recursive relation, matrix
algorithms, algorithms that calculate Binet’s formula and an algorithm
that uses binomial coefficients. In the second part we present the results of
experimental comparison of the above algorithms which were implemented
in C programming language using GNU MP library for arbitrary precision
arithmetic. |
Sekundarne ključne besede: |
Fibonacci numbers;arbitrary precision arithmetic;time complexity;recursion;computer science;diploma;Računalništvo;Univerzitetna in visokošolska dela; |
Vrsta dela (COBISS): |
Diplomsko delo/naloga |
Študijski program: |
1000468 |
Konec prepovedi (OpenAIRE): |
1970-01-01 |
Komentar na gradivo: |
Univ. v Ljubljani, Fak. za računalništvo in informatiko |
Strani: |
60 str. |
ID: |
14444843 |