binary multiplication this is a method to find ab in a time complexity of olog b this is one of the most commonly used methods of finding result of multiplication also useful in cases where solution to abc is required where a b c can be numbers over the computers calculation limits done using iteration can also be done using recursion let s say you need to calculate a b rule 1 a b aa b2 example 4 4 44 42 8 2 rule 2 if b is odd then a b a a b 1 where b 1 is even once b is even repeat the process to get a b repeat the process until b 1 or b 0 because a1 a and a0 0 as far as the modulo is concerned the fact ab c ac bc c now apply rule 1 or 2 whichever is required chinmoy159 multiply a and b using bitwise multiplication parameters a int the first number b int the second number returns int a b examples binarymultiply2 3 6 binarymultiply5 0 0 binarymultiply3 4 12 binarymultiply10 5 50 binarymultiply0 5 0 binarymultiply2 1 2 binarymultiply1 10 10 calculate a b c using binary multiplication and modular arithmetic parameters a int the first number b int the second number modulus int the modulus returns int a b modulus examples binarymodmultiply2 3 5 1 binarymodmultiply5 0 7 0 binarymodmultiply3 4 6 0 binarymodmultiply10 5 13 11 binarymodmultiply2 1 5 2 binarymodmultiply1 10 3 1 multiply a and b using bitwise multiplication parameters a int the first number b int the second number returns int a b examples binary_multiply 2 3 6 binary_multiply 5 0 0 binary_multiply 3 4 12 binary_multiply 10 5 50 binary_multiply 0 5 0 binary_multiply 2 1 2 binary_multiply 1 10 10 calculate a b c using binary multiplication and modular arithmetic parameters a int the first number b int the second number modulus int the modulus returns int a b modulus examples binary_mod_multiply 2 3 5 1 binary_mod_multiply 5 0 7 0 binary_mod_multiply 3 4 6 0 binary_mod_multiply 10 5 13 11 binary_mod_multiply 2 1 5 2 binary_mod_multiply 1 10 3 1
def binary_multiply(a: int, b: int) -> int:
    
    res = 0
    while b > 0:
        if b & 1:
            res += a

        a += a
        b >>= 1

    return res


def binary_mod_multiply(a: int, b: int, modulus: int) -> int:
    
    res = 0
    while b > 0:
        if b & 1:
            res = ((res % modulus) + (a % modulus)) % modulus

        a += a
        b >>= 1

    return res


if __name__ == "__main__":
    import doctest

    doctest.testmod()