Full_mental's blog

By Full_mental, history, 5 weeks ago, In English,

hello codeforces , I am a beginner coder , you can imagine very beginner , I am trying to code matrix exponential for nth fibonacci number , but , I find a bug.

the fibonacci series is : 0,1,1,2,3,5,8,13,21.... my code generates : 0,1,1,2,5,21,144,1597,28657.....

please help me finding the bug , I oblige :( :( my code : https://paste.ubuntu.com/26187218/

 
 
 
 
  • Vote: I like it  
  • -5
  • Vote: I do not like it  

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Full_mental (previous revision, new revision, compare).

»
5 weeks ago, # |
Rev. 4   Vote: I like it +1 Vote: I do not like it

main_mat[0][0] = 1; main_mat[0][1] = 1; main_mat[1][0] = 1; main_mat[1][1] = 0;

Firstly, add this lines at the top of your while loop that is inside your int main function. Then you'll get the correct answer. If you do not include this line, then every time you input the value of n the values of element in main_mat 2D array is not initialized to its default value. You can check by yourself.

Secondly, your program is too slow. I'm not sure whether you used the fast exponentiation technique. You can find the nth fibonacci number in O(2^3*logn) = O(8*logn) time. But you are doing it in O(n*2^3) = O(8*n) time which is too slow. You need to learn fast exponentiation technique. :)
****

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Thank a lot vaiya :) ami bug paisilm na

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I know that i should use bigmod instead of the loop , then , the power will be calculated in O(log n) , but i am a beginner , so I started from easy approach