How to avoid overflow in modular multiplication ? | Java program for modular multiplication without any overflow ; To compute ( a * b ) % mod ; long res = 0 ; Initialize result ; If b is odd , add ' a ' to result ; Multiply ' a ' with 2 ; Divide b by 2 ; Return result ; Driver code
class GFG { static long mulmod ( long a , long b , long mod ) { a = a % mod ; while ( b > 0 ) { if ( b % 2 == 1 ) { res = ( res + a ) % mod ; } a = ( a * 2 ) % mod ; b /= 2 ; } return res % mod ; } public static void main ( String [ ] args ) { long a = 9223372036854775807L , b = 9223372036854775807L ; System . out . println ( mulmod ( a , b , 100000000000L ) ) ; } }