An algorithm to calculate the sum of Fibonacci Sequence: \(\mathrm{F}(n) +
\mathrm{F}(n+1) + .. + \mathrm{F}(m)\).
More...
#include <cassert>
#include <iostream>
#include <vector>
|
namespace | math |
| for IO operations
|
|
namespace | fibonacci_sum |
| Functions for the sum of the Fibonacci Sequence: \(\mathrm{F}(n) +
\mathrm{F}(n+1) + .. + \mathrm{F}(m)\).
|
|
An algorithm to calculate the sum of Fibonacci Sequence: \(\mathrm{F}(n) +
\mathrm{F}(n+1) + .. + \mathrm{F}(m)\).
An algorithm to calculate the sum of Fibonacci Sequence: \(\mathrm{F}(n) + \mathrm{F}(n+1) + .. + \mathrm{F}(m)\) where \(\mathrm{F}(i)\) 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
◆ fiboSum()
uint64_t math::fibonacci_sum::fiboSum |
( |
uint64_t | n, |
|
|
uint64_t | m ) |
Function to compute sum of fibonacci sequence from n to m.
- Parameters
-
n | start of sequence |
m | end of sequence |
- Returns
- uint64_t the sum of sequence
90 {
92}
uint64_t result(uint64_t n)
Definition fibonacci_sum.cpp:76
◆ main()
Main function.
- Returns
- 0 on exit
136 {
138 return 0;
139}
static void test()
Definition fibonacci_sum.cpp:101
◆ multiply()
Function to multiply two matrices
- Parameters
-
- Returns
- resultant matrix
39 {
41
42
43 result[0][0] = T[0][0] * A[0][0] + T[0][1] * A[1][0];
44 result[0][1] = T[0][0] * A[0][1] + T[0][1] * A[1][1];
45 result[1][0] = T[1][0] * A[0][0] + T[1][1] * A[1][0];
46 result[1][1] = T[1][0] * A[0][1] + T[1][1] * A[1][1];
47
49}
◆ power()
Function to compute A^n where A is a matrix.
- Parameters
-
- Returns
- resultant matrix
57 {
59 if (ex == 0 || ex == 1) {
60 return T;
61 }
62
65 if (ex & 1) {
67 }
68 return T;
69}
int multiply(int x, int res[], int res_size)
Definition power_for_huge_numbers.cpp:25
void power(int x, int n)
Definition power_for_huge_numbers.cpp:56
◆ result()
uint64_t math::fibonacci_sum::result |
( |
uint64_t | n | ) |
|
Function to compute sum of fibonacci sequence from 0 to n.
- Parameters
-
- Returns
- uint64_t ans, the sum of sequence
76 {
79 uint64_t ans = T[0][1];
80 ans = (ans - 1);
81 return ans;
82}
◆ test()
Function for testing fiboSum function. test cases and assert statement.
- Returns
void
101 {
102 uint64_t n = 0, m = 3;
106
107 n = 3;
108 m = 5;
112
113 n = 5;
114 m = 7;
118
119 n = 7;
120 m = 10;
122 assert(test_4 == 123);
124
125 n = 9;
126 m = 12;
128 assert(test_5 == 322);
130}
uint64_t fiboSum(uint64_t n, uint64_t m)
Definition fibonacci_sum.cpp:90
static void test_1()
Definition heavy_light_decomposition.cpp:505
static void test_2()
Definition heavy_light_decomposition.cpp:549
static void test_3()
Definition heavy_light_decomposition.cpp:592