Full_mental's blog

Help me debug the problem
By Full_mental, history, 6 years 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

Comments Comments (3)
| Write comment?
»
6 years 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. :)
****

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Thank a lot vaiya :) ami bug paisilm na

    → Reply
  • »
    »
    6 years 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

    → Reply