Integer overflow in Russian Peasant Algorithm in c++

Question

I came across a problem of Russian Peasant Exponentiation (RPE) Link is here which evaluates exponents much faster than the conventional method for finding x raised to the power of n.

Conventional Method

int power(int base, int exponent) {
    int result = 1;
    for(register int i = 1; i <= exponent; i++) {
        result *= base;
    }
    return result;
}

I implemented the algorithm for complex numbers, given that the multiplication can lead to overflow i am printing the re(z) mod m and im(z) mod mas 2 space separated integers, but my implementation is not correct as it is causing some weird answers can anyone point out the problem, and how to correct it. Here is my code

#include<iostream>
#include<complex>
using namespace std;

class Solution {
    int m;
    long long int k;
    complex<long long int> num;
    complex<long long int> russianPeasantExponentiation(), multiply(complex<long long int>, complex<long long int>);
public:
    void takeInput(), solve();
};

void Solution::takeInput() {
    int a, b;
    cin >> a >> b >> k >> m;
    num = complex<long long int> (a, b);
}

void Solution::solve() {
    complex<long long int> res = russianPeasantExponentiation();
    cout << real(res) << " " << imag(res) << endl;
}

complex<long long int> Solution::russianPeasantExponentiation() {
    complex<long long int> temp1(1, 0), temp2 = num;
    while(k) {
        if(k % 2) {
            temp1 = multiply(temp1, temp2);
        }
        temp2 = multiply(temp2, temp2);
        k /= 2;
    }
    return temp1;
}

complex<long long int> Solution::multiply(complex<long long int> a, complex<long long int> b) {
    long long int ar = real(a), ai = imag(a), br = real(b), bi = imag(b);
    complex<long long int> result(((ar * br) % m - (ai * bi) % m) % m, ((ar * bi)%m + (ai * br)%m)%m);
    return result;
}

int main() {
    int q;
    cin >> q;
    while(q--) {
        Solution obj;
        obj.takeInput();
        obj.solve();
    }
    return 0;
}

The questions states that input consists of an integer q which defines the no. of queries. Each query consists of 4 numbers separated by space a, b, k, m. For each query i have to find z = (a + ib)^k since the values of re(z) and im(z) can be very large so i have to print re(z) mod m and im(z) mod m

The problem is occuring in the test case of 8 2 10 1000000000 where the expected out put is 880332800 927506432 and my out put is -119667200 -72493568

Answer 1

This is such a neat algorithm I ended up writing my own!

I don't see how reducing intermediate results during the computation will make the maths work, quite the opposite.

Using complex<double> worked, though.

I planned on adding this algorithm to my toolbox, so It's a bit different than your implementation. I used the paper's algorithm, which yields 1 less multiplication. The way to deal with the modulus of negative numbers is in main()

#include <complex>
#include <iostream>

template <typename T>
T fastExp(T x, unsigned int e)
{
    if (e == 0)
        return T(1);

    while (!(e & 1))
    {
        x *= x;
        e >>= 1;
    }

    auto y = x;
    e >>= 1;
    while (e)
    {
        x *= x;
        if (e & 1)
            y *= x;
        e >>= 1;
    }
    return y;
}


int main()
{
    std::complex<double> x{ 8, 2 };

    auto y = fastExp(x, 10);

    long long k = 1000000000LL;

    std::complex<double> z;
    y -= { floor(y.real() / k), floor(y.imag() / k) };

    std::complex<long long> r{ (long long)y.real(), (long long)y.imag() };
    while (r.real() < 0)
        r._Val[0] += k;

    while (r.imag() < 0)
        r._Val[1] += k;

    std::cout << "result: " << r.real() << " + " << r.imag() << " i" << "\n";
}

Answer 2

You need to replace

((ar * br) % m - (ai * bi) % m) % m

with

((ar * br) % m + m - (ai * bi) % m) % m

because you can get a negative value as a result of the expression above