Faster computation of Fibonacci series. More...

#include <cinttypes>
#include <cstdio>
#include <iostream>
#include <cassert>
#include <string>
#include <stdexcept>

Include dependency graph for fibonacci_fast.cpp:

Functions
uint64_t	fib (uint64_t n)
	Function to compute the nth Fibonacci number.

static void	test ()
	Function to test the Fibonacci computation.

int	main ()
	Main Function.

Variables
constexpr uint64_t	MAX = 93
	for std::invalid_argument

Detailed Description

Faster computation of Fibonacci series.

An efficient way to calculate nth fibonacci number faster and simpler than \(O(n\log n)\) method of matrix exponentiation. This works by using both recursion and dynamic programming. As 93rd fibonacci exceeds 19 digits, which cannot be stored in a single long long variable, we can only use it till 92nd fibonacci we can use it for 10000th fibonacci etc, if we implement bigintegers. This algorithm works with the fact that nth fibonacci can easily found if we have already found \(n/2\)th or \((n+1)/2\)th fibonacci. It is a property of fibonacci similar to matrix exponentiation.

Author: Krishna Vedala

See also: fibonacci_large.cpp, fibonacci.cpp, string_fibonacci.cpp

Definition in file fibonacci_fast.cpp.

Function Documentation

◆ fib()

uint64_t fib ( uint64_t n )

Function to compute the nth Fibonacci number.

Parameters

n	The index of the Fibonacci number to compute

Returns: uint64_t The nth Fibonacci number

Definition at line 38 of file fibonacci_fast.cpp.

                         {
    // Using static keyword will retain the values of
    // f1 and f2 for the next function call.
    static uint64_t f1 = 1, f2 = 1;
 
    if (n <= 2) {
        return f2;
    } if (n >= MAX) {
        throw std::invalid_argument("Cannot compute for n>=" + std::to_string(MAX) +
                                    " due to limit of 64-bit integers");
        return 0;
    }
    
    // We do not need temp to be static.
    uint64_t temp = f2;  
    f2 += f1;
    f1 = temp;
 
    return f2;
}

◆ main()

int main ( void )

Main Function.

Returns: 0 on exit

Definition at line 175 of file fibonacci_fast.cpp.

           {
    test();  // run self-test implementations
    return 0;
}

◆ test()

static void test ( )

static

Function to test the Fibonacci computation.

Returns: void

Definition at line 63 of file fibonacci_fast.cpp.

                   {
    // Test for valid Fibonacci numbers
    assert(fib(1) == 1);
    assert(fib(2) == 1);
    assert(fib(3) == 2);
    assert(fib(4) == 3);
    assert(fib(5) == 5);
    assert(fib(6) == 8);
    assert(fib(7) == 13);
    assert(fib(8) == 21);
    assert(fib(9) == 34);
    assert(fib(10) == 55);
    assert(fib(11) == 89);
    assert(fib(12) == 144);
    assert(fib(13) == 233);
    assert(fib(14) == 377);
    assert(fib(15) == 610);
    assert(fib(16) == 987);
    assert(fib(17) == 1597);
    assert(fib(18) == 2584);
    assert(fib(19) == 4181);
    assert(fib(20) == 6765);
    assert(fib(21) == 10946);
    assert(fib(22) == 17711);
    assert(fib(23) == 28657);
    assert(fib(24) == 46368);
    assert(fib(25) == 75025);
    assert(fib(26) == 121393);
    assert(fib(27) == 196418);
    assert(fib(28) == 317811);
    assert(fib(29) == 514229);
    assert(fib(30) == 832040);
    assert(fib(31) == 1346269);
    assert(fib(32) == 2178309);
    assert(fib(33) == 3524578);
    assert(fib(34) == 5702887);
    assert(fib(35) == 9227465);
    assert(fib(36) == 14930352);
    assert(fib(37) == 24157817);
    assert(fib(38) == 39088169);
    assert(fib(39) == 63245986);
    assert(fib(40) == 102334155);
    assert(fib(41) == 165580141);
    assert(fib(42) == 267914296);
    assert(fib(43) == 433494437);
    assert(fib(44) == 701408733);
    assert(fib(45) == 1134903170);
    assert(fib(46) == 1836311903);
    assert(fib(47) == 2971215073);
    assert(fib(48) == 4807526976);
    assert(fib(49) == 7778742049);
    assert(fib(50) == 12586269025);
    assert(fib(51) == 20365011074);
    assert(fib(52) == 32951280099);
    assert(fib(53) == 53316291173);
    assert(fib(54) == 86267571272);
    assert(fib(55) == 139583862445);
    assert(fib(56) == 225851433717);
    assert(fib(57) == 365435296162);
    assert(fib(58) == 591286729879);
    assert(fib(59) == 956722026041);
    assert(fib(60) == 1548008755920);
    assert(fib(61) == 2504730781961);
    assert(fib(62) == 4052739537881);
    assert(fib(63) == 6557470319842);
    assert(fib(64) == 10610209857723);
    assert(fib(65) == 17167680177565);
    assert(fib(66) == 27777890035288);
    assert(fib(67) == 44945570212853);
    assert(fib(68) == 72723460248141);
    assert(fib(69) == 117669030460994);
    assert(fib(70) == 190392490709135);
    assert(fib(71) == 308061521170129);
    assert(fib(72) == 498454011879264);
    assert(fib(73) == 806515533049393);
    assert(fib(74) == 1304969544928657);
    assert(fib(75) == 2111485077978050);
    assert(fib(76) == 3416454622906707);
    assert(fib(77) == 5527939700884757);
    assert(fib(78) == 8944394323791464);
    assert(fib(79) == 14472334024676221);
    assert(fib(80) == 23416728348467685);
    assert(fib(81) == 37889062373143906);
    assert(fib(82) == 61305790721611591);
    assert(fib(83) == 99194853094755497);
    assert(fib(84) == 160500643816367088);
    assert(fib(85) == 259695496911122585);
    assert(fib(86) == 420196140727489673);
    assert(fib(87) == 679891637638612258);
    assert(fib(88) == 1100087778366101931);
    assert(fib(89) == 1779979416004714189);
    assert(fib(90) == 2880067194370816120);
    assert(fib(91) == 4660046610375530309);
    assert(fib(92) == 7540113804746346429);
 
    // Test for invalid Fibonacci numbers
    try {
        fib(MAX + 1);
        assert(false && "Expected an invalid_argument exception to be thrown");
    } catch (const std::invalid_argument& e) {
        const std::string expected_message = "Cannot compute for n>=" + std::to_string(MAX) +
                                             " due to limit of 64-bit integers";
        assert(e.what() == expected_message);
    }
 
    std::cout << "All Fibonacci tests have successfully passed!\n";
}

Variable Documentation

◆ MAX

uint64_t MAX = 93

constexpr

for std::invalid_argument

for uint64_t for standard IO for IO operations for assert for std::to_string

Maximum Fibonacci number that can be computed

The result after 93 cannot be stored in a uint64_t data type.

Definition at line 31 of file fibonacci_fast.cpp.

Functions