+ 1

How to optimize the code for modular exponentation, to make the program run faster?

I have assignment in college to make the program in C++ for computing modular exponents. The task is: Input: In the first line of input is an integer t (1<=t<=100000) is given which specifies the number of tests. Each test is given by three integers: a, b, m as defined above (1<=a<=109, 0<=b<=109, 1<=m<=106). Output: You should write t lines, the answer to the query: (ab)%m. Example For the input data 2 3 2 10 4 3 10 the correct answer is 9 4 And my code is: #include <iostream> using namespace std; int main() { int t; cin>>t; for (int i=0; i<t; i++) { int a,b,m; long long int x, result = 1; cin >>a>>b>>m; x=a; do { x%=m; if (b&1) { result*=x; result%=m; } x*=x; } while (b>>=1); cout <<result<<endl; } return 0; } And my question is how to optimize this code, because it is running correctly but my teachers program (online Themis - an on line problem judge) is saying that "time limit exceeded" and i can't pass. So i have to do something that help the program counted faster.

4th Jan 2021, 8:36 PM
Martyna Tomaszewska
Martyna Tomaszewska - avatar
4 Respuestas
+ 2
There is a great Khan Academy article about optimizing this. You need to implement it in code https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/fast-modular-exponentiation
6th Jan 2021, 3:37 AM
Tejaswi Hegde
Tejaswi Hegde - avatar
0
How it will be in code? I have to change all my code or just optimize this one? What will be the best?
12th Jan 2021, 8:20 PM
Martyna Tomaszewska
Martyna Tomaszewska - avatar
0
Since these are different approaches, you will need to re write your code.
13th Jan 2021, 2:45 AM
Tejaswi Hegde
Tejaswi Hegde - avatar
0
Thanks:) solved
17th Jan 2021, 5:38 PM
Martyna Tomaszewska
Martyna Tomaszewska - avatar