Answers to: modulo of big numbershttps://discuss.codechef.com/questions/2825/modulo-of-big-numbers<p>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 <a href="http://opc.iarcs.org.in/index.php/problems/01TILES">question</a>.</p>
<pre><code>#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);
}
</code></pre>
<p>P.S. I am just a beginner.</p>enSun, 07 Oct 2012 20:41:23 +0530Comment by aroravipul113 on betlista's answerhttps://discuss.codechef.com/questions/2825/modulo-of-big-numbers#2901<p>Ya i got it wrong in the first go.Thanks for Your help :D</p>aroravipul113Sun, 07 Oct 2012 20:41:23 +0530https://discuss.codechef.com/questions/2825/modulo-of-big-numbers#2901Comment by aroravipul113 on pragrame's answerhttps://discuss.codechef.com/questions/2825/modulo-of-big-numbers#2900<p>ya this is what I was looking for thanks.:P</p>aroravipul113Sun, 07 Oct 2012 20:39:35 +0530https://discuss.codechef.com/questions/2825/modulo-of-big-numbers#2900Comment by pragrame on pragrame's answerhttps://discuss.codechef.com/questions/2825/modulo-of-big-numbers#2869<p>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;"</p>pragrameFri, 05 Oct 2012 22:47:18 +0530https://discuss.codechef.com/questions/2825/modulo-of-big-numbers#2869Comment by aroravipul113 on pragrame's answerhttps://discuss.codechef.com/questions/2825/modulo-of-big-numbers#2868<p>@programe Thanks it worked :D 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 ???</p>aroravipul113Fri, 05 Oct 2012 21:36:34 +0530https://discuss.codechef.com/questions/2825/modulo-of-big-numbers#2868Comment by betlista on betlista's answerhttps://discuss.codechef.com/questions/2825/modulo-of-big-numbers#2852<p>problem is, that in <code>t2</code> there is value before mod operation ;-)</p>betlistaThu, 04 Oct 2012 22:40:59 +0530https://discuss.codechef.com/questions/2825/modulo-of-big-numbers#2852Answer by pragramehttps://discuss.codechef.com/questions/2825/modulo-of-big-numbers/2849<p>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 <em>after</em> 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.</p>
<p>Instead, you may like to do the following:</p>
<blockquote>
<p>t3 = t1 + t2;</p>
<p>t3 = t3 % 15746;</p>
<p>t1 = t2;</p>
<p>t2 = t3;</p>
</blockquote>
<p>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.</p>pragrameThu, 04 Oct 2012 22:03:15 +0530https://discuss.codechef.com/questions/2825/modulo-of-big-numbers/2849Comment by aroravipul113 on betlista's answerhttps://discuss.codechef.com/questions/2825/modulo-of-big-numbers#2845<p>I have tried it but still i am getting wrong answer.</p>
<p>my updated code was</p>
<pre>#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; return="" (0);="" }=""></pre>aroravipul113Thu, 04 Oct 2012 21:43:52 +0530https://discuss.codechef.com/questions/2825/modulo-of-big-numbers#2845Answer by betlistahttps://discuss.codechef.com/questions/2825/modulo-of-big-numbers/2830<p>You used correct operand <code>%</code>, but on wrong place, put it in your for loop, otherwise it can overflow.</p>betlistaThu, 04 Oct 2012 14:58:01 +0530https://discuss.codechef.com/questions/2825/modulo-of-big-numbers/2830