Question

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

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:
    Scala Long is 64‑bit signed.
    We reduce modulo at every step to keep values safe.
*/

object ModMulProgram {

  // -------------------------------------------------------------
  // SLOW VERSION (simple, correct, but extremely slow)
  // -------------------------------------------------------------
  def mulModSlow(a: Long, b: Long, mod: Long): Long = {
    /*
        Computes:
            (b + b + b + ... a times) % mod

        This avoids overflow because:
            - result stays below mod
            - b fits in Long
            - 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) {
      val tmp = aa
      aa = bb
      bb = tmp
    }

    var result = 0L

    var i = 0L
    while (i < aa) {
      result = (result + bb) % mod
      i += 1
    }

    result
  }


  // -------------------------------------------------------------
  // FAST VERSION (efficient and safe)
  // -------------------------------------------------------------
  def mulModFast(a: Long, b: Long, mod: Long): Long = {
    /*
        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 = 0L

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

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

    result
  }


  // -------------------------------------------------------------
  // MAIN PROGRAM
  // -------------------------------------------------------------
  def main(args: Array[String]): Unit = {
    val x   = 798345L
    val y   = 20289473612815L
    val mod = 100000000000003L

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

    println(s"Slow result: $slowResult")
    println(s"Fast result: $fastResult")
  }
}


/*
run:

Slow result: 99811422305238
Fast result: 99811422305238

*/

 

70+ SQL courses for beginners and professionals