To perform operations on large numbers efficiently (such as addition, subtraction, multiplication, division, and exponentiation), you need algorithms that go beyond basic arithmetic due to limitations in standard data types and performance concerns. Here’s a breakdown of optimized algorithms commonly used in handling large numbers:
1. Addition and Subtraction
Algorithm:
- Represent numbers as strings or arrays (digits).
- Start from the least significant digit and propagate carry/borrow.
- Time Complexity: O(n) where n is the number of digits.
Optimization:
- Use digit grouping (e.g., base 1e4 or 1e9) to reduce the number of iterations.
2. Multiplication
Naive Method:
- Multiply digit by digit → O(n²)
Optimized Algorithms:
Karatsuba Algorithm
- Divide and conquer method.
- Time Complexity: O(n^log₂3) ≈ O(n^1.585)
Fast Fourier Transform (FFT)
- Use FFT to do convolution (polynomial multiplication).
- Time Complexity: O(n log n)
Toom-Cook Multiplication
- Generalization of Karatsuba, used in GMP.
- Time Complexity: Between O(n^1.4) and O(n^1.6)
3. Division
Long Division
- Similar to manual process.
- Time Complexity: O(n²)
Newton-Raphson Division
- Uses Newton-Raphson method for reciprocal approximation.
- Time Complexity: O(n log n) with FFT-based multiplication.
4. Exponentiation
Exponentiation by Squaring
- Divide-and-conquer approach.
- Time Complexity: O(log e) multiplications
def power(a, b):
result = 1
while b > 0:
if b % 2 == 1:
result *= a
a *= a
b //= 2
return result
- For large numbers, use modular exponentiation with large base modulus (like RSA crypto).
5. Modular Arithmetic (mod m)
Important in cryptography and number theory.
Modular Multiplication
def mod_mult(a, b, m):
return (a * b) % m
Modular Exponentiation (for very large exponents)
def mod_pow(a, b, m):
result = 1
a = a % m
while b > 0:
if b % 2 == 1:
result = (result * a) % m
a = (a * a) % m
b //= 2
return result
Libraries for Large Number Arithmetic
- Python: Built-in int handles arbitrary precision.
- Java: BigInteger
- C++: No built-in, but use libraries like:
- JavaScript: Use BigInt
Summary Table
| Operation | Naive Time | Optimized Time | Best Algo |
|---|---|---|---|
| Addition/Sub | O(n) | O(n) | Manual with carry |
| Multiplication | O(n²) | O(n log n) | FFT / Karatsuba |
| Division | O(n²) | O(n log n) | Newton-Raphson |
| Exponentiation | O(n) | O(log n) | Exp by Squaring |