This program computes the N^th Fibonacci number in modulo mod input argument .
More...
#include <iostream>
#include <vector>
#include <cassert>
|
uint64_t | fibo (uint64_t n, uint64_t mod) |
|
void | test () |
|
int | main () |
|
This program computes the N^th Fibonacci number in modulo mod input argument .
Takes O(logn) time to compute nth Fibonacci number
- Author
- villayatali123
-
[unknown author]()
- See also
- fibonacci.cpp, fibonacci_fast.cpp, string_fibonacci.cpp, fibonacci_large.cpp
◆ fibo()
uint64_t fibo |
( |
uint64_t | n, |
|
|
uint64_t | mod ) |
This function finds nth fibonacci number in a given modulus
- Parameters
-
n | nth fibonacci number |
mod | modulo number |
24{
28 n--;
30 Identity[0][0]=1; Identity[0][1]=0;
31 Identity[1][0]=0; Identity[1][1]=1;
32
33 transition[0][0]=0;
34 transition[1][0]=transition[1][1]=transition[0][1]=1;
35
36 while(n)
37 {
38 if(n%2)
39 {
41 for(int i=0;i<2;i++)
42 {
43 for(int j=0;j<2;j++)
44 {
46 {
47 res[i][j]=(res[i][j]%mod+((Identity[i][
k]%mod*transition[
k][j]%mod))%mod)%mod;
48 }
49 }
50 }
51 for(int i=0;i<2;i++)
52 {
53 for(int j=0;j<2;j++)
54 {
55 Identity[i][j]=res[i][j];
56 }
57 }
58 n--;
59 }
60 else{
62 for(int i=0;i<2;i++)
63 {
64 for(int j=0;j<2;j++)
65 {
67 {
68 res1[i][j]=(res1[i][j]%mod+((transition[i][
k]%mod*transition[
k][j]%mod))%mod)%mod;
69 }
70 }
71 }
72 for(int i=0;i<2;i++)
73 {
74 for(int j=0;j<2;j++)
75 {
76 transition[i][j]=res1[i][j];
77 }
78 }
79 n=n/2;
80 }
81 }
82 return ((result[0]%mod*Identity[0][0]%mod)%mod+(result[1]%mod*Identity[1][0]%mod)%mod)%mod;
83}
double k(double x)
Another test function.
Definition composite_simpson_rule.cpp:117
uint64_t result(uint64_t n)
Definition fibonacci_sum.cpp:76
◆ main()
Main function
107{
109 uint64_t mod=1000000007;
113}
uint64_t fibo(uint64_t n, uint64_t mod)
Definition fibonacci_matrix_exponentiation.cpp:23
void test()
Definition fibonacci_matrix_exponentiation.cpp:88
◆ test()
Function to test above algorithm
89{
90 assert(
fibo(6, 1000000007 ) == 8);
92 assert(
fibo(5, 1000000007 ) == 5);
94 assert(
fibo(10 , 1000000007) == 55);
96 assert(
fibo(500 , 100) == 25);
98 assert(
fibo(500 , 10000) == 4125);
101}