Question

How to do modulo multiplication for 64‑bit values without using BigInteger in Swift

Answer 1

/*
===============================================================
    Modulo Multiplication (Slow and Fast Versions)
===============================================================

Purpose:
    Compute (a * b) % mod safely for large 64‑bit values.

Versions:
    1. Slow version:
        - Adds b to result a times.
        - Always correct.
        - Very slow for large numbers.
        - Useful as a correctness reference.

    2. Fast version:
        - Uses the classic "double‑and‑add" technique.
        - Runs in O(log b).
        - Avoids overflow by never multiplying large numbers.
        - Produces the same result as the slow version.

Notes:
    Swift UInt64 arithmetic wraps on overflow, so the fast version
    reduces modulo at every step to keep values safe.
*/


// ---------------------------------------------------------------
// SLOW VERSION (simple, correct, but extremely slow)
// ---------------------------------------------------------------
func mulModSlow(_ a: UInt64, _ b: UInt64, _ mod: UInt64) -> UInt64 {
    /*
        Computes:
            (b + b + b + ... a times) % mod

        This avoids overflow because:
            - result stays below mod
            - b fits in UInt64
            - addition is safe

        But it is O(a), which is too slow for large inputs.
    */

    var aa = a
    var bb = b

    // Reduce loop count by ensuring the smaller number is used as counter
    if bb < aa {
        swap(&aa, &bb)
    }

    var result: UInt64 = 0

    for _ in 0..<aa {
        result = (result &+ bb) % mod
    }

    return result
}


// ---------------------------------------------------------------
// FAST VERSION (efficient and safe)
// ---------------------------------------------------------------
func mulModFast(_ a: UInt64, _ b: UInt64, _ mod: UInt64) -> UInt64 {
    /*
        Uses the "double‑and‑add" method:

            - If the lowest bit of b is set, add a to result.
            - Double a each step.
            - Shift b right each step.

        This avoids overflow because:
            - We never compute a * b directly.
            - Doubling a is safe because we reduce modulo each step.

        This makes the algorithm:
            - Fast
            - Safe
            - Exact
    */

    var aa = a % mod
    var bb = b
    var result: UInt64 = 0

    while bb > 0 {
        if (bb & 1) == 1 {
            result = (result &+ aa) % mod
        }

        aa = (aa << 1) % mod
        bb >>= 1
    }

    return result
}


// ---------------------------------------------------------------
// MAIN PROGRAM
// ---------------------------------------------------------------
let x: UInt64   = 798_345
let y: UInt64   = 20_289_473_612_815
let mod: UInt64 = 100_000_000_000_003

let slowResult = mulModSlow(x, y, mod)
let fastResult = mulModFast(x, y, mod)

print("Slow result: \(slowResult)")
print("Fast result: \(fastResult)")



/*
run:

Slow result: 99811422305238
Fast result: 99811422305238

*/

 

70+ SQL courses for beginners and professionals