How to calculate -1 modulo 1000000007 in C++

Question

I tried to get the result of -1 modulo 1000000007 using the % operator of C++ and fmod function.
The output is -1, but -1 modulo 1000000007==1000000006.

What have I done wrong?

Answer 1

Plainly said, you took the wrong operator.

C++ and C % is not modulo, but remainder.

assert(a / b * b + a % b == a); // for integral types

If a is non-negative, modulo and remainder are the same.

Otherwise the return-value is negative, just add b.

template<class T>
inline constexpr auto
modulo(T a, T b) -> decltype(a%b) {
    auto r = a % b;
    if (r < 0) r += b;
    return r;
}

Or (also) for C:

#define modulo(a, b) (a % b < 0 ? a % b + b : a % b)

For completeness: Before C++11, a / b could always round down instead of always to 0, though C++03 already had a note that the next standard would probably mandate rounding to 0.

See Wikipedia on modulo:

Modulo is the remainder of euclidiean division, and always in range 0 <= modulo < divisor

And on remainder:

In mathematics, the remainder is the amount "left over" after performing some computation.