“Multiply two integers without using the multiplication operator.”

A few months ago I had a technical interview for a data science consulting firm. I was only asked one question, and it seemed so outlandishly removed from the job role that I wondered whether the interviewers had mistaken me for a candidate for another vacancy.

It was simply this:

“Write a function that multiplies two integers (positive or negative) without using the multiplication operator.”

The interviewers said they were fine with pseudocode.

I was sharing my screen on one of those snazzy online coding platforms. Within seconds, they said they wanted working code.

I chose to use Python – it was in the job requirements after all – and promptly wrote the most obvious code imaginable.

def multiply_by_summation(a, b):
    result = 0
    for _ in range(abs(b)):
        result += a
    return -result if b < 0 else result

They asked whether I could optimise this, so I added a line to find the smaller of the two absolute values of a and b, and loop over the smaller one. I was asked to make it faster than O(|b|).

Then they seemed to get tired of the whole thing, and that was that.

I didn’t get the job.

The classic interview answer is of course so-called Russian peasant multiplication. It is huge misnomer. The method was used in Ancient Egypt, and why Russian peasant? Because of Vladimir Golenischev?

Anyway, here it is. The method relies on successive halving and doubling. It runs in O(log b) time. 

def multiply_egyptian(a, b):
    if a == 0 or b == 0:
        return 0
    # Make a positive, remember sign
    negative = (a < 0) ^ (b < 0)
    a, b = abs(a), abs(b)
    
    result = 0
    while b > 0:
        if b & 1:           # if b is odd
            result += a
        a <<= 1             # a = a * 2
        b >>= 1             # b = b // 2
    return -result if negative else result

An even faster algorithm is Karatsuba multiplication, which should rightfully be called Russian multiplicaiton, since it was invented by the Russian Anatoly Karatsuba. This has a time complexity of O(n1.58n ), where n is the number of digits.

def add_n_times(base, times):
    """Add 'base' to itself 'times' times: base * times without '*'."""
    result = 0
    for _ in range(times):
        result += base
    return result

def pow10(n):
    """Compute 10**n using only addition (no '*', no '**')."""
    if n == 0:
        return 1
    # Build iteratively: pow10(n) = pow10(n-1) * 10 = add pow10(n-1) ten times
    result = 1
    for _ in range(n):
        result = add_n_times(result, 10)  # result * 10
    return result

def multiply_bit_only(a, b):
    """O(log n) multiplication using only bits/addition (for base case)."""
    if a == 0 or b == 0:
        return 0
    negative = (a < 0) != (b < 0)
    a, b = abs(a), abs(b)
    result = 0
    while b > 0:
        if b & 1:
            result += a
        a <<= 1  # a *= 2 (bit shift allowed, as it's not '*')
        b >>= 1  # b //= 2
    return -result if negative else result

def karatsuba_no_multiply(x, y):
    """Full Karatsuba without any '*': recursive, O(n^1.58) asymptotically."""
    # Base case: small numbers use bit multiplication
    if abs(x) < 10 or abs(y) < 10:
        return multiply_bit_only(x, y)
    
    # Handle signs
    negative = (x < 0) != (y < 0)
    x, y = abs(x), abs(y)
    if x < y:
        x, y = y, x
    
    # Digits in smaller number
    n = len(str(y))
    half = (n + 1) // 2  # Ceiling of n/2
    
    # Split using div/mod 
    divider = pow10(half)
    x_high = x // divider
    x_low = x % divider
    y_high = y // divider
    y_low = y % divider
    
    # 3 recursions instead of 4
    z0 = karatsuba_no_multiply(x_low, y_low)
    z2 = karatsuba_no_multiply(x_high, y_high)
    z1 = karatsuba_no_multiply(x_low + x_high, y_low + y_high) - z2 - z0
    
    # Combine without '*': use add_n_times for the "shifts" (powers of 10)
    pow_half = divider  # Already 10**half
    pow_double = add_n_times(pow_half, pow_half)  #
    
    double_half = add_n_times(half, 2)
    pow_double = pow10(double_half)
    
    # Now "z2 * pow_double" = add z2, pow_double times
    part_high = add_n_times(z2, pow_double)
    # "z1 * pow_half" = add z1, pow_half times
    part_mid = add_n_times(z1, pow_half)
    
    # Total: part_high + part_mid + z0
    result = part_high + part_mid + z0
    return -result if negative else result