Ways to do modulo multiplication with primitive types

modulo multiplication

primitive types

arithmetic operations

programming techniques

computational methods

Ways to do modulo multiplication with primitive types

Master System Design with Codemia

Enhance your system design skills with over 120 practice problems, detailed solutions, and hands-on exercises.

Start Practicing Learn More

Introduction

Modular multiplication computes (a * b) % m where a, b, and m are integers. The challenge is that a * b may overflow the primitive integer type (e.g., 64-bit int) before the modulo can be applied. For example, multiplying two numbers near 2^63 overflows a 64-bit signed integer even though the final result after modulo fits easily. This article covers techniques to compute (a * b) % m safely with primitive types: using modular properties, Russian peasant multiplication, 128-bit intermediates, and language-specific solutions in C++, Java, and Python.

The Overflow Problem

1// C/C++ example: overflow on 64-bit multiplication
2#include <stdint.h>
3#include <stdio.h>
4
5int main() {
6    int64_t a = 1000000007LL;
7    int64_t b = 1000000007LL;
8    int64_t m = 1000000009LL;
9
10    // a * b = 1000000014000000049 — fits in 64-bit (barely)
11    int64_t result = (a * b) % m;
12    printf("%lld\n", result);  // Correct: 999999986
13
14    // But with larger values:
15    int64_t x = 9223372036854775000LL;  // Near INT64_MAX
16    int64_t y = 2LL;
17    // x * y overflows 64-bit signed int — undefined behavior in C!
18    return 0;
19}

Method 1: Modular Arithmetic Properties

The key property: (a * b) % m = ((a % m) * (b % m)) % m

cpp

1// C++: reduce before multiplying
2long long mulmod(long long a, long long b, long long m) {
3    a %= m;
4    b %= m;
5    return (a * b) % m;
6}

This only helps if a or b is much larger than m. If both a and b are already less than m but a * b overflows, this does not prevent the overflow.

Method 2: Russian Peasant Multiplication (Binary Method)

Computes (a * b) % m using repeated doubling, avoiding any multiplication larger than 2 * m:

cpp

1// C++: overflow-safe modular multiplication
2long long mulmod(long long a, long long b, long long m) {
3    long long result = 0;
4    a %= m;
5    while (b > 0) {
6        if (b & 1) {
7            result = (result + a) % m;  // Add if bit is set
8        }
9        a = (a * 2) % m;  // Double a
10        b >>= 1;           // Shift b right
11    }
12    return result;
13}
14
15// Example: (10^18 * 10^18) % (10^9 + 7)
16int main() {
17    long long a = 1000000000000000000LL;
18    long long b = 1000000000000000000LL;
19    long long m = 1000000007LL;
20    printf("%lld\n", mulmod(a, b, m));  // Safe, no overflow
21    return 0;
22}

Time complexity: O(log b) — one iteration per bit of b. This is the standard approach for competitive programming.

Python Implementation

python

1def mulmod(a, b, m):
2    """Russian peasant modular multiplication."""
3    result = 0
4    a %= m
5    while b > 0:
6        if b & 1:
7            result = (result + a) % m
8        a = (a * 2) % m
9        b >>= 1
10    return result
11
12# Python has arbitrary precision, so this is mainly for demonstration
13# In practice, Python just does (a * b) % m directly
14print(mulmod(10**18, 10**18, 10**9 + 7))

Python integers have arbitrary precision, so overflow is not an issue. Use pow(a, b, m) for modular exponentiation.

Method 3: 128-bit Intermediates (C/C++)

GCC and Clang support __int128 for intermediate calculations:

cpp

1#include <cstdint>
2#include <cstdio>
3
4long long mulmod(long long a, long long b, long long m) {
5    return ((__int128)a * b) % m;
6}
7
8int main() {
9    long long a = 9000000000000000000LL;
10    long long b = 9000000000000000000LL;
11    long long m = 1000000007LL;
12    printf("%lld\n", mulmod(a, b, m));  // Correct
13    return 0;
14}

This is the simplest and fastest solution when __int128 is available (GCC/Clang on 64-bit systems). MSVC does not support __int128.

Method 4: Java Solutions

Java does not have unsigned 64-bit integers or __int128. Use Math.floorMod, BigInteger, or manual methods:

java

1import java.math.BigInteger;
2
3public class ModMul {
4    // Method 1: BigInteger (safe but slow)
5    static long mulmod(long a, long b, long m) {
6        return BigInteger.valueOf(a)
7                .multiply(BigInteger.valueOf(b))
8                .mod(BigInteger.valueOf(m))
9                .longValue();
10    }
11
12    // Method 2: Math.multiplyHigh (Java 9+) + Barrett reduction
13    static long mulmodFast(long a, long b, long m) {
14        // For values where a*b fits in long
15        a = Math.floorMod(a, m);
16        b = Math.floorMod(b, m);
17        return Math.floorMod(a * b, m);
18    }
19
20    // Method 3: Russian peasant multiplication
21    static long mulmodBinary(long a, long b, long m) {
22        long result = 0;
23        a = Math.floorMod(a, m);
24        while (b > 0) {
25            if ((b & 1) == 1) {
26                result = Math.floorMod(result + a, m);
27            }
28            a = Math.floorMod(a * 2, m);
29            b >>= 1;
30        }
31        return result;
32    }
33
34    public static void main(String[] args) {
35        long a = 1_000_000_000_000_000_000L;
36        long b = 1_000_000_000_000_000_000L;
37        long m = 1_000_000_007L;
38        System.out.println(mulmod(a, b, m));       // Safe with BigInteger
39        System.out.println(mulmodBinary(a, b, m));  // Safe with binary method
40    }
41}

Method 5: Modular Exponentiation

(a^n) % m uses repeated squaring with modular multiplication:

cpp

1long long power(long long base, long long exp, long long mod) {
2    long long result = 1;
3    base %= mod;
4    while (exp > 0) {
5        if (exp & 1) {
6            result = mulmod(result, base, mod);  // Use safe mulmod
7        }
8        base = mulmod(base, base, mod);
9        exp >>= 1;
10    }
11    return result;
12}
13
14// Example: (2^1000000) % (10^9 + 7)
15long long ans = power(2, 1000000, 1000000007);

Method Summary

Method	Overflow-Safe?	Speed	Availability
`(a%m * b%m) % m`	Only if `m < 2^32`	O(1)	All languages
Russian peasant	Yes	O(log b)	All languages
`__int128` intermediate	Yes	O(1)	GCC/Clang only
`BigInteger`	Yes	O(n^2)	Java
Python native `%`	Yes (arbitrary precision)	O(1) amortized	Python

Common Pitfalls

Assuming (a * b) % m is safe without checking ranges: In C/C++ and Java, if a * b overflows the integer type, the result is undefined behavior (C/C++) or wraps around (Java). Always verify that a and b are small enough for direct multiplication, or use a safe method.
Forgetting to reduce a and b before multiplication: Even with the Russian peasant method, reduce a %= m first. If a > m, the additions inside the loop can still overflow when a + result > INT64_MAX.
Using __int128 on MSVC or 32-bit systems: __int128 is a GCC/Clang extension on 64-bit platforms. It is not available on MSVC or 32-bit targets. Use the binary method or BigInteger as a portable alternative.
Not using Python's built-in pow(a, b, m) for modular exponentiation: Python's three-argument pow() is implemented in C and uses efficient modular exponentiation internally. Writing your own is slower and unnecessary.
Confusing modulo behavior with negative numbers: C/C++ % can return negative values for negative operands. Use ((a % m) + m) % m to guarantee a non-negative result. Java's Math.floorMod() handles this correctly.

Summary

The core challenge is that a * b may overflow before % m can be applied
Russian peasant multiplication (binary method) is the universal O(log b) solution for any language
Use __int128 intermediates in GCC/Clang for the simplest and fastest solution
In Java, use BigInteger for correctness or the binary method for performance
Python has arbitrary-precision integers, so (a * b) % m works directly without overflow concerns