diplomsko delo
Gašper Močnik (Avtor), Jurij Mihelič (Mentor)

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:
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 Povezava se bo odprla v novem oknu
Št. ogledov: 164
Št. prenosov: 39
Ocena: 0 (0 glasov)
Metapodatki: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

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