2 years ago

#48221

test-img

Andrew

Implementing Modular exponentiation in C++

The following C++ program uses modular exponentiation to compute the quantity ((0.75 + 2.25*(9^((1e+7-2)/2) ))) mod (1e+9+7). This is done using the powxy function, which takes x and y as arguments and returnx x^y mod (1e+9+7). The computed value, 692336617, is incorrect and the correct answer is 192336614. There is a similar problem in computing ((0.75 + 2.25*(9^((300-2)/2) ))) mod (1e+9+7), which I entered in Wolfram Alpha. The answer differs from the correct answer, 327873818, but many of the digits are the same. Can anyone explains why the computed values are incorrect or how the program can be changed?


#include <iostream> 

using namespace std;
 
const int M = 1e9 + 7;

long long int powxy(long long int x, long long int y) {
    if (y == 0) return 1;
    if (y&1) return (x*powxy(x, y-1))%M;
    long long int t = powxy(x, y/2);
    return (t*t)%M;
} 
 
int main() {
    int m = 1;
    long long int n = 10000000; 
    
    int num = 4999999; //num = (1e+7-2)/2 
     
    //int num = 149; 
    long long int res = powxy(9,num)*2.25+0.75; //if num = 149, should equal ((0.75 + 2.25*(9^((300-2)/2) ))) mod (1e+9+7)
       
    
    cout << res;  
    return 0;
}

c++

modular-arithmetic

0 Answers

Your Answer

Accepted video resources