A Deep Dive into Recursive Integer Multiplication

25 January 2025

Problem definition

Integer multiplication dates back to around 3,000 BCE, with the earliest multiplication algorithm developed by the Egyptians. Since then, there has been a lot of research on better approaches, which culminated in the discovery of the Karatsuba multiplication algorithm by Anatoly Karatsuba in 1960. Today, understanding the principles behind integer multiplication remains highly relevant, as the foundation of modern AI relies on millions of matrix multiplications.

An alternate approach to grade school multiplication is recursive integer multiplication. We start by building the mathematical intuition behind this algorithm.

Note: This algorithm is adapted from "Algorithms Illuminated" by Tim Roughgarden.

Mathematical foundation

We start by defining the inputs and outputs for this algorithm. The inputs are two numbers, $x$ and $y$. It is assumed that both, $x$ and $y$, are even numbers.

The output is an integer, that is the product of $x$ and $y$.

Lets define $n$ as the length of $x$ and $y$.

The first step is to split $x$ and $y$ into two digits of length, $n/2$. A number can be expressed in terms of its higher order and lower order halve by:

Since we want to calculate $x.y$:

Using the distributive law, we arrive at:

$10^n \cdot (a \cdot c)$: Contribution of the higher-order digits.
$10^{n/2} \cdot (a \cdot d + b \cdot c)$: Cross terms between higher and lower-order digits.
$b \cdot d$: Contribution of the lower-order digits.

Algorithm description

The algorithm is developed as a recursive function. In general, a recursive algorithm has a base case and a recursive case.

Step 1: Define inputs, outputs and assumptions

Input: Two even integers $x$ and $y$
Output: The product of $x$ and $y$
Assumption: The number of digits is a power of 2

Step 2: Define the base case

If $x$ and $y$ are single digit numbers i.e. $n = 1$, we directly compute $x.y$ using grade school multiplication as $x.y$.

Step 3: Define the recursive case

If $x$ and $y$ are larger than single digit numbers, they are split into their higher order and lower order halves, $a$, $b$, $c$ and $d$.

Now the required components are $a.c$, $a.d$, $b.c$ and $b.d$. These are recursively computed.

Lastly, all the components are brought together using grade school multiplication and addition.

The pseudocode for the recursive integer multiplication is given as follows:

    Algorithm: rec-int-mult
    Input: two n-digit positive integers x and y
    Output: their product (x × y)
    Assumption: n must be a power of 2
    
    // Base Case
    if n equals 1 then
        return x × y
    // Recursive Case
    else
        // Calculate the higher order and lower order halves
        a, b = first and second halves of x
        c, d = first and second halves of y
        
        // Recursively multiply the components
        ac = RecIntMult(a, c)
        ad = RecIntMult(a, d)
        bc = RecIntMult(b, c)
        bd = RecIntMult(b, d)
        
        // Combine using grade school multiplication and addition
        return 10^n × ac + 10^(n/2) × (ad + bc) + bd
    

Implementation

"""Implements the recursive integer multiplication (RecIntMult) algorithm from Algorithms Illuminated.

This module provides an efficient method for multiplying large integers using recursion.
"""

import math


def count_digits(number: int) -> int:
    """Return the number of decimal digits in an integer.

    Args:
        number: An integer whose digits are to be counted

    Returns:
        int: The number of digits (e.g., 1 for 0, 3 for 123).
    """

    if number == 0:
        return 1

    return math.floor(math.log10(abs(number))) + 1


def rec_int_mult(x: int, y: int) -> int:
    """Multiply two positive even integers recursively using the RecIntMult algorithm.

    This implements a divide-and-conquer approach to integer multiplication.
    Assumes inputs are positive even integers; behavior is undefined for negative numbers.

    Args:
        x: First positive even integer
        y: Second positive even integer

    Returns:
        int: The product of x and y.
    """

    if x < 10 and y < 10:
        return x * y

    digits_x = count_digits(x)
    digits_y = count_digits(y)

    n = max(digits_x, digits_y)

    # Split x into higher order (a) and lower order (b) parts based on half its digits
    a = x // (10**(digits_x//2))
    b = x % (10**(digits_x//2))

    # Split y into higher order (c) and lower order (d) parts
    c = y // (10**(digits_y//2))
    d = y % (10**(digits_y//2))

    # Recursively compute subproducts
    ac = rec_int_mult(a, c)
    ad = rec_int_mult(a, d)
    bc = rec_int_mult(b, c)
    bd = rec_int_mult(b, d)

    # Combine results: ac * 10^n + (ad + bc) * 10^(n/2) + bd
    term_1 = 10**n * ac
    term_2 = 10**(n // 2) * (ad + bc)
    term_3 = bd

    return term_1 + term_2 + term_3


if __name__ == "__main__":
    # Verify the algorithm with a simple test case
    assert rec_int_mult(24, 36) == 24 * 36
    print("All tests passed!")