RetroSearch Browse

Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Showing content from https://TheAlgorithms.github.io/C-Plus-Plus/de/dc3/fibonacci__sum_8cpp.html below:

TheAlgorithms/C++: math/fibonacci_sum.cpp File Reference

Searching...

No Matches

An algorithm to calculate the sum of Fibonacci Sequence: \(\mathrm{F}(n) + \mathrm{F}(n+1) + .. + \mathrm{F}(m)\). More...

#include <cassert>
#include <cstdint>
#include <iostream>
#include <vector>

Go to the source code of this file.

namespace math for assert
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

Definition in file fibonacci_sum.cpp.

◆ matrix using math::fibonacci_sum::matrix = std::vector<std::vector<uint64_t> >

Definition at line 31 of file fibonacci_sum.cpp.

◆ 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

Definition at line 91 of file fibonacci_sum.cpp.

91 {

93}

uint64_t result(uint64_t n)

◆ main() ◆ multiply() math::fibonacci_sum::matrix math::fibonacci_sum::multiply ( const math::fibonacci_sum::matrix & T, const math::fibonacci_sum::matrix & A )

Function to multiply two matrices

Parameters

Returns: resultant matrix

Definition at line 39 of file fibonacci_sum.cpp.

40 {

41

math::fibonacci_sum::matrix

result

(2, std::vector<uint64_t>(2, 0));

42

43

44 result

[0][0] = T[0][0] * A[0][0] + T[0][1] * A[1][0];

45 result

[0][1] = T[0][0] * A[0][1] + T[0][1] * A[1][1];

46 result

[1][0] = T[1][0] * A[0][0] + T[1][1] * A[1][0];

47 result

[1][1] = T[1][0] * A[0][1] + T[1][1] * A[1][1];

48

50}

◆ power()

Function to compute A^n where A is a matrix.

Parameters

Returns: resultant matrix

Definition at line 58 of file fibonacci_sum.cpp.

58 {

59 math::fibonacci_sum::matrix A{{1, 1}, {1, 0}};

60 if (ex == 0 || ex == 1) {

61 return T;

62 }

63

64

T =

power

(T, ex / 2);

66 if (ex & 1) {

68 }

69 return T;

70}

math::fibonacci_sum::matrix power(math::fibonacci_sum::matrix T, uint64_t ex)

math::fibonacci_sum::matrix multiply(const math::fibonacci_sum::matrix &T, const math::fibonacci_sum::matrix &A)

◆ 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

Definition at line 77 of file fibonacci_sum.cpp.

77 {

78 math::fibonacci_sum::matrix T{{1, 1}, {1, 0}};

80 uint64_t ans = T[0][1];

81 ans = (ans - 1);

82 return ans;

83}

◆ test()

Function for testing fiboSum function. test cases and assert statement.

Returns: void

Definition at line 102 of file fibonacci_sum.cpp.

102 {

103 uint64_t n = 0, m = 3;

106 std::cout << "Passed Test 1!" << std::endl;

107

108 n = 3;

109 m = 5;

112 std::cout << "Passed Test 2!" << std::endl;

113

114 n = 5;

115 m = 7;

118 std::cout << "Passed Test 3!" << std::endl;

119

120 n = 7;

121 m = 10;

123 assert(test_4 == 123);

124 std::cout << "Passed Test 4!" << std::endl;

125

126 n = 9;

127 m = 12;

129 assert(test_5 == 322);

130 std::cout << "Passed Test 5!" << std::endl;

131}

uint64_t fiboSum(uint64_t n, uint64_t m)

RetroSearch is an open source project built by @garambo | Open a GitHub Issue

Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo

HTML: 3.2 | Encoding: UTF-8 | Version: 0.7.4