Imports System
Module ModMulProgram
'===============================================================
' Modulo Multiplication (Slow and Fast Versions)
'===============================================================
'
'Purpose:
' Compute (a * b) Mod mod safely for large 64‑bit values
' without using BigInteger.
'
'Versions:
' 1. Slow version:
' - Adds b to result a times.
' - Always correct.
' - Very slow for large numbers.
'
' 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:
' VB.NET Long = 64‑bit signed integer.
' All intermediate values are kept safe using modulo.
'===============================================================
'---------------------------------------------------------------
' SLOW VERSION (simple, correct, but extremely slow)
'---------------------------------------------------------------
Function MulModSlow(a As Long, b As Long, modv As Long) As Long
' Reduce loop count by ensuring the smaller number is used as counter
If b < a Then
Dim tmp = a
a = b
b = tmp
End If
Dim resultv As Long = 0
' Perform: result = (b + b + ... a times) Mod modv
For i As Long = 0 To a - 1
resultv = (resultv + b) Mod modv
Next
Return resultv
End Function
'---------------------------------------------------------------
' FAST VERSION (efficient and safe)
'---------------------------------------------------------------
Function MulModFast(a As Long, b As Long, modv As Long) As 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
'
Dim resultv As Long = 0
a = a Mod modv
While b > 0
If (b And 1) = 1 Then
resultv = (resultv + a) Mod modv
End If
a = (a << 1) Mod modv
b >>= 1
End While
Return resultv
End Function
'---------------------------------------------------------------
' MAIN PROGRAM
'---------------------------------------------------------------
Sub Main()
Dim x As Long = 798345
Dim y As Long = 20289473612815
Dim modv As Long = 100000000000003
Dim slowResult = MulModSlow(x, y, modv)
Dim fastResult = MulModFast(x, y, modv)
Console.WriteLine("Slow result: " & slowResult)
Console.WriteLine("Fast result: " & fastResult)
End Sub
End Module
' run:
'
' Slow result: 99811422305238
' Fast result: 99811422305238
'
