Enum MultiplicationAlgorithm 

pub enum MultiplicationAlgorithm {
    Standard,
    Schoolbook,
    Karatsuba,
    ToomCook,
    FFT,
}

Multiplication algorithms for multi-limb arithmetic.

This enum defines different algorithms for multiplying large multi-precision integers (BigInt). Each algorithm offers different trade-offs between performance, memory usage, and complexity. The choice of algorithm depends on the size of the operands and the computational requirements.

Performance Characteristics

• Standard/Schoolbook: O(n²) - Simple, good for small numbers
• Karatsuba: O(n^1.585) - Good balance for medium-sized numbers
• Toom-Cook: O(n^1.465) - Better for large numbers, more complex
• FFT: O(n log n) - Optimal for very large numbers, highest overhead

Memory Usage

Different algorithms have different memory requirements and may allocate temporary BigInt values during computation.

Algorithm Selection

The library automatically selects appropriate algorithms based on operand sizes, but this enum allows manual override for specific use cases.

Variants

Standard

Standard long multiplication (schoolbook algorithm).

This is the traditional “grade school” multiplication method that multiplies each digit of one number by each digit of the other. Simple to implement and optimal for small numbers.

Complexity: O(n²) Memory: O(1) additional space Best for: Numbers with < 1000 bits

Schoolbook

Alias for Standard multiplication algorithm.

Provided for clarity and compatibility. Same performance characteristics as Standard.

Karatsuba

Karatsuba multiplication algorithm.

Reduces the multiplication of two n-digit numbers to three multiplications of n/2-digit numbers using the identity: (a₁·2^(n/2) + a₀) · (b₁·2^(n/2) + b₀) = a₁b₁·2^n + (a₁b₁ + a₀b₀ - (a₀+a₁)(b₀+b₁))·2^(n/2) + a₀b₀

Complexity: O(n^1.585) Memory: O(n) additional space Best for: Numbers with 1000-10000 bits

ToomCook

Toom-Cook multiplication algorithm (Toom-3 variant).

Generalizes Karatsuba by splitting numbers into more parts and evaluating at multiple points. Uses polynomial interpolation to reconstruct the result. This implementation uses a simplified 3-way split with evaluation at points 0, 1, -1, 2, and ∞.

Complexity: O(n^1.465) Memory: O(n) additional space Best for: Numbers with 10000-50000 bits

FFT

Fast Fourier Transform (FFT) based multiplication.

Uses FFT to multiply large numbers by converting them to the frequency domain. Requires the numbers to be treated as coefficients of polynomials. Most efficient asymptotically but has high constant factors and memory requirements.

Complexity: O(n log n) Memory: O(n) additional space Best for: Numbers with >50000 bits Note: May fall back to Toom-Cook for smaller sizes due to overhead

Trait Implementations

impl Clone for MultiplicationAlgorithm

fn clone(&self) -> MultiplicationAlgorithm

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for MultiplicationAlgorithm

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl PartialEq for MultiplicationAlgorithm

fn eq(&self, other: &MultiplicationAlgorithm) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl Copy for MultiplicationAlgorithm

impl Eq for MultiplicationAlgorithm

impl StructuralPartialEq for MultiplicationAlgorithm