You are not logged in. Please login at www.codechef.com to post your questions!

×

modulo of big numbers

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.

asked 03 Oct '12, 21:03

aroravipul113's gravatar image

2★aroravipul113
19116
accept rate: 0%

edited 04 Oct '12, 14:55

betlista's gravatar image

3★betlista ♦♦
16.9k49115225


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.

link

answered 04 Oct '12, 22:03

pragrame's gravatar image

6★pragrame ♦♦
973568379
accept rate: 14%

@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 ???

(05 Oct '12, 21:36) aroravipul1132★

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;"

(05 Oct '12, 22:47) pragrame ♦♦6★

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

(07 Oct '12, 20:39) aroravipul1132★

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

link

answered 04 Oct '12, 14:58

betlista's gravatar image

3★betlista ♦♦
16.9k49115225
accept rate: 11%

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

my updated code was

#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);="" }="">
(04 Oct '12, 21:43) aroravipul1132★

problem is, that in t2 there is value before mod operation ;-)

(04 Oct '12, 22:40) betlista ♦♦3★

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

(07 Oct '12, 20:41) aroravipul1132★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×342

question asked: 03 Oct '12, 21:03

question was seen: 2,359 times

last updated: 07 Oct '12, 20:41