Introduction
Computing a * b / c with integers can overflow during the intermediate multiplication a * b, even when the final result fits in the target type. For example, with 32-bit integers, 1_000_000 * 1_000_000 / 1_000_000 should be 1_000_000, but the intermediate product 1_000_000_000_000 exceeds INT32_MAX (2,147,483,647). The MulDiv pattern solves this by using a wider intermediate type, restructuring the arithmetic, or using specialized instructions. Windows provides MulDiv() in its API for this exact purpose.
The Problem
1#include <stdint.h>
2#include <stdio.h>
3
4int32_t a = 1000000;
5int32_t b = 1000000;
6int32_t c = 1000000;
7
8// OVERFLOW: a * b = 1,000,000,000,000 > INT32_MAX (2,147,483,647)
9int32_t result = a * b / c; // Undefined behavior in C/C++
10printf("%d\n", result); // Garbage value or crash
The final answer is 1,000,000 which fits in int32_t, but the intermediate multiplication overflows.
The simplest and most portable solution:
1// C: cast to int64_t before multiplying
2int32_t muldiv(int32_t a, int32_t b, int32_t c) {
3 return (int32_t)((int64_t)a * (int64_t)b / (int64_t)c);
4}
5
6int32_t result = muldiv(1000000, 1000000, 1000000);
7// (int64_t)1000000 * 1000000 = 1,000,000,000,000 (fits in int64_t)
8// / 1000000 = 1,000,000 (fits in int32_t)
1// C++
2int32_t muldiv(int32_t a, int32_t b, int32_t c) {
3 return static_cast<int32_t>(static_cast<int64_t>(a) * b / c);
4}
1// Java: int is 32-bit, long is 64-bit
2int muldiv(int a, int b, int c) {
3 return (int)((long)a * b / c);
4}
# Python: integers have arbitrary precision — no overflow possible
result = a * b // c
This works when the wider type (64-bit) can hold the intermediate product. For 64-bit inputs, you need 128-bit arithmetic.
Solution 2: Windows MulDiv() Function
Windows provides a built-in function:
1#include <windows.h>
2
3// MulDiv(a, b, c) computes (a * b + c/2) / c with 64-bit intermediate
4int result = MulDiv(1000000, 1000000, 1000000);
5// Returns 1000000
6
7// MulDiv rounds to nearest integer (not truncation)
8int result2 = MulDiv(10, 3, 7); // (10 * 3 + 7/2) / 7 = 33/7 ≈ 4.7 → 5
MulDiv also handles the rounding correctly (rounds to nearest, not toward zero).
Solution 3: Restructure the Arithmetic
If you know the relationship between values, restructure to avoid large intermediates:
1// If a is divisible by c, divide first
2int32_t muldiv_restructured(int32_t a, int32_t b, int32_t c) {
3 // a * b / c = (a / c) * b + (a % c) * b / c
4 return (a / c) * b + (a % c) * b / c;
5}
6
7// Example: 1000000 * 999999 / 1000000
8// = (1000000 / 1000000) * 999999 + (1000000 % 1000000) * 999999 / 1000000
9// = 1 * 999999 + 0 * 999999 / 1000000
10// = 999999
This is the Russian Peasant approach and works without wider types:
1// General case: a * b / c without overflow (approximate)
2int32_t muldiv_safe(int32_t a, int32_t b, int32_t c) {
3 int32_t q = a / c;
4 int32_t r = a % c;
5 // a * b / c = q * b + r * b / c
6 // If r * b might still overflow, apply recursively or use wider type
7 return q * b + (int32_t)((int64_t)r * b / c);
8}
When a and b are 64-bit, their product can exceed 64 bits:
1// GCC/Clang: __int128 extension
2int64_t muldiv64(int64_t a, int64_t b, int64_t c) {
3 return (int64_t)((__int128)a * b / c);
4}
1// Rust: u128 / i128 are native types
2fn muldiv(a: i64, b: i64, c: i64) -> i64 {
3 ((a as i128) * (b as i128) / (c as i128)) as i64
4}
1// C#: no 128-bit integer, use BigInteger
2using System.Numerics;
3
4int MulDiv(long a, long b, long c) {
5 return (int)((BigInteger)a * b / c);
6}
Solution 5: Scaling / Fixed-Point Arithmetic
In graphics and audio, values are often in fixed-point format. MulDiv is used to scale between representations:
1// Fixed-point 16.16 format: value * 65536
2// To multiply two fixed-point numbers: (a * b) >> 16
3// But (a * b) can overflow 32 bits
4
5int32_t fixed_mul(int32_t a, int32_t b) {
6 // a and b are in 16.16 fixed point
7 return (int32_t)(((int64_t)a * b) >> 16);
8}
9
10// Scale a value proportionally: value * numerator / denominator
11int32_t scale(int32_t value, int32_t num, int32_t den) {
12 return (int32_t)((int64_t)value * num / den);
13}
14
15// Example: scale 480 pixels by 16/9 aspect ratio
16int32_t width = scale(480, 16, 9); // 853
Rounding Behavior
1// Truncation (toward zero) — default for integer division
2int32_t truncate_muldiv(int32_t a, int32_t b, int32_t c) {
3 return (int32_t)((int64_t)a * b / c);
4}
5
6// Round to nearest (like Windows MulDiv)
7int32_t round_muldiv(int32_t a, int32_t b, int32_t c) {
8 int64_t product = (int64_t)a * b;
9 // Add c/2 for positive, subtract c/2 for negative
10 if ((product >= 0 && c > 0) || (product < 0 && c < 0))
11 return (int32_t)((product + c / 2) / c);
12 else
13 return (int32_t)((product - c / 2) / c);
14}
15
16// Example: 10 * 3 / 7
17truncate_muldiv(10, 3, 7); // 30/7 = 4 (truncated)
18round_muldiv(10, 3, 7); // (30 + 3) / 7 = 4 (rounded, same here)
19// 10 * 5 / 7
20truncate_muldiv(10, 5, 7); // 50/7 = 7 (truncated from 7.14)
21round_muldiv(10, 5, 7); // (50 + 3) / 7 = 7 (rounded)
Common Pitfalls
Assuming the compiler promotes to a wider type: In C/C++, int32_t * int32_t produces int32_t, not int64_t. You must explicitly cast at least one operand to the wider type before the multiplication: (int64_t)a * b.
Overflow in the wider type too: int64_t * int64_t can overflow int64_t. If both operands are close to INT64_MAX, even 64-bit intermediate arithmetic overflows. Use __int128 (GCC/Clang), BigInteger (C#/Java), or a multi-precision library.
Division by zero: MulDiv with c = 0 is undefined. Windows MulDiv() returns -1 when c = 0, which is a sentinel value, not a meaningful result. Always check for zero divisor.
Signed vs unsigned overflow: Signed integer overflow is undefined behavior in C/C++. Unsigned overflow wraps around (modular arithmetic). If you rely on wrapping, use unsigned types explicitly.
Ignoring the remainder: a * b / c truncates toward zero. For financial or proportional calculations, consider rounding to nearest or using the (a * b + c/2) / c pattern for unbiased rounding.
Summary
a * b / c can overflow during a * b even when the final result fits in the target type
Cast to a wider type before multiplying: (int64_t)a * b / c for 32-bit inputs
Use __int128 (GCC/Clang) or BigInteger (C#/Java) for 64-bit inputs
Windows provides MulDiv() which uses 64-bit intermediate and rounds to nearest
Restructure as (a/c)*b + (a%c)*b/c to avoid wider types when possible
Python has arbitrary-precision integers and never overflows
