Modular Arithmetic Code Implementations
Complete Modular Arithmetic code implementations in C++, Python, Java, and JavaScript with time and space complexity analysis on AntInLoop.
Read Modular Arithmetic Guide ยท Launch Interactive Visualizer
C++ Implementation
// Modular Arithmetic in C++
#include <iostream>
class ModularArithmetic {
public:
static int modAdd(int a, int b, int mod) {
return ((a % mod) + (b % mod)) % mod;
}
static int modSub(int a, int b, int mod) {
return ((a % mod) - (b % mod) + mod) % mod;
}
static int modMul(int a, int b, int mod) {
return ((long long)(a % mod) * (b % mod)) % mod;
}
static int modPow(int base, int exponent, int mod) {
int result = 1;
base %= mod;
while (exponent > 0) {
if (exponent % 2 == 1)
result = (int)((1LL * result * base) % mod);
base = (int)((1LL * base * base) % mod);
exponent /= 2;
}
return result;
}
// Modular inverse using Fermat's Little Theorem (mod must be prime)
static int modInverse(int a, int mod) {
return modPow(a, mod - 2, mod);
}
};JAVA Implementation
// Modular Arithmetic in Java
public class ModularArithmetic {
public static int modAdd(int a, int b, int mod) {
return ((a % mod) + (b % mod)) % mod;
}
public static int modSub(int a, int b, int mod) {
return ((a % mod) - (b % mod) + mod) % mod;
}
public static int modMul(int a, int b, int mod) {
return ((a % mod) * (b % mod)) % mod;
}
public static int modPow(int base, int exponent, int mod) {
int result = 1;
base = base % mod;
while (exponent > 0) {
if ((exponent & 1) == 1)
result = (int)((long)result * base % mod);
base = (int)((long)base * base % mod);
exponent >>= 1;
}
return result;
}
// Modular inverse using Fermat's Little Theorem (mod must be prime)
public static int modInverse(int a, int mod) {
return modPow(a, mod - 2, mod);
}
}JAVASCRIPT Implementation
// Modular Arithmetic in JavaScript
function modAdd(a, b, mod) {
return ((a % mod) + (b % mod)) % mod;
}
function modSub(a, b, mod) {
return ((a % mod) - (b % mod) + mod) % mod;
}
function modMul(a, b, mod) {
return ((a % mod) * (b % mod)) % mod;
}
function modPow(base, exponent, mod) {
let result = 1;
base = base % mod;
while (exponent > 0) {
if (exponent % 2 === 1) {
result = (result * base) % mod;
}
base = (base * base) % mod;
exponent = Math.floor(exponent / 2);
}
return result;
}
// Modular inverse using Fermat's Little Theorem (mod must be prime)
function modInverse(a, mod) {
return modPow(a, mod - 2, mod);
}PYTHON Implementation
# Modular Arithmetic in Python
def mod_add(a, b, mod):
return (a % mod + b % mod) % mod
def mod_sub(a, b, mod):
return (a % mod - b % mod + mod) % mod
def mod_mul(a, b, mod):
return (a % mod * b % mod) % mod
def mod_pow(base, exponent, mod):
result = 1
base %= mod
while exponent > 0:
if exponent % 2:
result = (result * base) % mod
base = (base * base) % mod
exponent //= 2
return result
# Modular inverse using Fermat's Little Theorem (mod must be prime)
def mod_inverse(a, mod):
return mod_pow(a, mod - 2, mod)