fibonacci_sum.cpp

/**
 * @file
 * @brief An algorithm to calculate the sum of [Fibonacci
 * Sequence](https://en.wikipedia.org/wiki/Fibonacci_number): \f$\mathrm{F}(n) +
 * \mathrm{F}(n+1) + .. + \mathrm{F}(m)\f$
 * @details An algorithm to calculate the sum of Fibonacci Sequence:
 * \f$\mathrm{F}(n) + \mathrm{F}(n+1) + .. + \mathrm{F}(m)\f$ where
 * \f$\mathrm{F}(i)\f$ denotes the i-th Fibonacci Number . Note that F(0) = 0
 * and F(1) = 1. The value of the sum is calculated using matrix exponentiation.
 * Reference source:
 * https://stackoverflow.com/questions/4357223/finding-the-sum-of-fibonacci-numbers
 * @author [Sarthak Sahu](https://github.com/SarthakSahu1009)
 */

#include <cassert>   /// for assert
#include <cstdint>
#include <iostream>  /// for std::cin and std::cout
#include <vector>    /// for std::vector

/**
 * @namespace math
 * @brief Mathematical algorithms
 */
namespace math {
/**
 * @namespace fibonacci_sum
 * @brief Functions for the sum of the Fibonacci Sequence: \f$\mathrm{F}(n) +
 * \mathrm{F}(n+1) + .. + \mathrm{F}(m)\f$
 */
namespace fibonacci_sum {
using matrix = std::vector<std::vector<uint64_t> >;

/**
 * Function to multiply two matrices
 * @param T matrix 1
 * @param A martix 2
 * @returns resultant matrix
 */
math::fibonacci_sum::matrix multiply(const math::fibonacci_sum::matrix &T,
                                     const math::fibonacci_sum::matrix &A) {
    math::fibonacci_sum::matrix result(2, std::vector<uint64_t>(2, 0));

    // multiplying matrices
    result[0][0] = T[0][0] * A[0][0] + T[0][1] * A[1][0];
    result[0][1] = T[0][0] * A[0][1] + T[0][1] * A[1][1];
    result[1][0] = T[1][0] * A[0][0] + T[1][1] * A[1][0];
    result[1][1] = T[1][0] * A[0][1] + T[1][1] * A[1][1];

    return result;
}

/**
 * Function to compute A^n where A is a matrix.
 * @param T matrix
 * @param ex power
 * @returns resultant matrix
 */
math::fibonacci_sum::matrix power(math::fibonacci_sum::matrix T, uint64_t ex) {
    math::fibonacci_sum::matrix A{{1, 1}, {1, 0}};
    if (ex == 0 || ex == 1) {
        return T;
    }

    T = power(T, ex / 2);
    T = multiply(T, T);
    if (ex & 1) {
        T = multiply(T, A);
    }
    return T;
}

/**
 * Function to compute sum of fibonacci sequence from 0 to n.
 * @param n number
 * @returns uint64_t ans, the sum of sequence
 */
uint64_t result(uint64_t n) {
    math::fibonacci_sum::matrix T{{1, 1}, {1, 0}};
    T = power(T, n);
    uint64_t ans = T[0][1];
    ans = (ans - 1);
    return ans;
}

/**
 * Function to compute sum of fibonacci sequence from n to m.
 * @param n start of sequence
 * @param m end of sequence
 * @returns uint64_t the sum of sequence
 */
uint64_t fiboSum(uint64_t n, uint64_t m) {
    return (result(m + 2) - result(n + 1));
}
}  // namespace fibonacci_sum
}  // namespace math

/**
 * Function for testing fiboSum function.
 * test cases and assert statement.
 * @returns `void`
 */
static void test() {
    uint64_t n = 0, m = 3;
    uint64_t test_1 = math::fibonacci_sum::fiboSum(n, m);
    assert(test_1 == 4);
    std::cout << "Passed Test 1!" << std::endl;

    n = 3;
    m = 5;
    uint64_t test_2 = math::fibonacci_sum::fiboSum(n, m);
    assert(test_2 == 10);
    std::cout << "Passed Test 2!" << std::endl;

    n = 5;
    m = 7;
    uint64_t test_3 = math::fibonacci_sum::fiboSum(n, m);
    assert(test_3 == 26);
    std::cout << "Passed Test 3!" << std::endl;

    n = 7;
    m = 10;
    uint64_t test_4 = math::fibonacci_sum::fiboSum(n, m);
    assert(test_4 == 123);
    std::cout << "Passed Test 4!" << std::endl;

    n = 9;
    m = 12;
    uint64_t test_5 = math::fibonacci_sum::fiboSum(n, m);
    assert(test_5 == 322);
    std::cout << "Passed Test 5!" << std::endl;
}

/**
 * @brief Main function
 * @returns 0 on exit
 */
int main() {
    test();  // execute the tests
    return 0;
}