diplomsko delo
Abstract
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.
Keywords
Fibonaccijeva števila;aritmetika poljubne natančnosti;časovna zahtevnost;rekurzija;univerzitetni študij;diplomske naloge;
Data
Language: |
Slovenian |
Year of publishing: |
2022 |
Typology: |
2.11 - Undergraduate Thesis |
Organization: |
UL FRI - Faculty of Computer and Information Science |
Publisher: |
[G. Močnik] |
UDC: |
004:51(043.2) |
COBISS: |
97925635
|
Views: |
164 |
Downloads: |
39 |
Average score: |
0 (0 votes) |
Metadata: |
|
Other data
Secondary language: |
English |
Secondary title: |
Comparison of algorithms for computing Fibonacci numbers |
Secondary abstract: |
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. |
Secondary keywords: |
Fibonacci numbers;arbitrary precision arithmetic;time complexity;recursion;computer science;diploma;Računalništvo;Univerzitetna in visokošolska dela; |
Type (COBISS): |
Bachelor thesis/paper |
Study programme: |
1000468 |
Embargo end date (OpenAIRE): |
1970-01-01 |
Thesis comment: |
Univ. v Ljubljani, Fak. za računalništvo in informatiko |
Pages: |
60 str. |
ID: |
14444843 |