modulo of big numbers

general
#1

I want to express the output(t3) as modulo of 15746 can someone please tell me what is the error in this code.(n<1000000)
for full question.

#include<iostream>
#include<algorithm>

using namespace std;

int main()
{
      int n,x,t1=0,t2=1,t3=0;
      cin>>n;
      for(x = 0 ;x < n ; x++)
      {
                   t3=t1+t2;
                   t1=t2;
                   t2=t3;
     }
      t3=t3%15746;
      cout << t3;
//system("pause");
                  return (0);
}

P.S. I am just a beginner.

1 Like
#2

You used correct operand %, but on wrong place, put it in your for loop, otherwise it can overflow.

#3

You need to put the modulus inside the for-loop. The problem is that after a while, t3 is going to overflow. In order to debug this, just ask yourself: “Is t1 < 15746? Is t2 < 15746? Is t3 <15746? after each iteration?”. In your updated code, you have put the modulus after assigning t3 to t2. This means that its still not going to work, because the ‘updated t3’ is not being used to calculate the next t1/t2.

Instead, you may like to do the following:

t3 = t1 + t2;

t3 = t3 % 15746;

t1 = t2;

t2 = t3;

Now you can see that after each iteration, assuming that t1 and t2 are <15746, then in the next iteration also, t1 and t2 will be < 15746.

4 Likes
#4

I have tried it but still i am getting wrong answer.

my updated code was

#include
#include

using namespace std;

int main()
{
      int n,x,t1=0,t2=1,t3=0;
      cin>>n;
      for(x=0;x < n;x++)
      {
                   t3=t1+t2;
                   t1=t2;
                   t2=t3;
                   t3=t3%15746;
     }

      cout<<t3;
      return (0);
}
#5

problem is, that in t2 there is value before mod operation :wink:

#6

@programe Thanks it worked :smiley: but suppose if we were able to compute till say 10^30 (t3 < 10^30) then take its modulus with 15746 will it stll give the same answer ???

#7

I think you mean t3 < 2^30. Yes it will work even then. 10^30 will not even fit in a long long. I suppose you’d then do something like “if (t3 >= (1<<30)) t3 = t3%15746;”

#8

ya this is what I was looking for thanks.:stuck_out_tongue:

#9

Ya i got it wrong in the first go.Thanks for Your help :smiley: