Algorithms Illuminated: Karatsuba multiplication 2/2

In the previous post, I presented the Karatsuba algorithm for fast multiplication of huge integers:

We showed one possible implementation using F#:

let rec karatsuba x y =
    let (+) x y = add x y
    let (-) x y = subtract x y
    let (<<<) x n = leftShift x n

    let xLength = List.length x
    let yLength = List.length y
    if yLength < 2 then
        multByOneDigit x y[0]
    elif xLength < 2 then
        multByOneDigit y x[0]
    else
        let n2 = (min xLength yLength) / 2
        let a, b = splitTail x n2
        let c, d = splitTail y n2
        let p = a + b
        let q = c + d
        let ac = karatsuba a c
        let bd = karatsuba b d
        let pq = karatsuba p q
        let adbc = pq - ac - bd
        (ac <<< n2*2) + (adbc <<< n2) + bd

Remember that x and y are expected to have lots of digits and that I chose to represent them with an int list, e.g., [5; 6; 7; 8]. We have already discussed the implementation of themultByOneDigit and splitTail functions, so now we are going to discuss add, subtract, and leftShift.

To add two lists of digits, we are going to follow the school grade algorithm:

Starting from the least significant part, i.e., from the last items on each list, we add the current digits and carry any overflow over 10. An imperative implementation of this procedure is:

let add x y =
    let mutable xPlusY = List.empty<int>
    let mutable carry = 0
    let mutable i = List.length x - 1
    let mutable j = List.length y - 1

    while i >= 0 || j >= 0 do
        let bruteSum = (if i >= 0 then x[i] else 0) + (if j >= 0 then y[j] else 0) + carry
        let newCarry, newDigit = if bruteSum >= 10 then 1, bruteSum - 10 else 0, bruteSum
        xPlusY <- newDigit :: xPlusY
        carry <- newCarry
        i <- i - 1
        j <- j - 1

    if carry > 0 then carry :: xPlusY else xPlusY

As x and y may have different lengths, each one has its own index, i and j respectively; at every step, we add a new digit to xPlusY and keep the overflow for the next step. As we said in the previous post, it is OK to use imperative code in F# when necessary, but it is also a good idea to consider a functional approach  like for example:

let add (x: int list) (y: int list) =
    let rec addCurrentDigit i j carry xPlusY =
        if i < 0 && j < 0 then
            if carry > 0 then carry :: xPlusY else xPlusY
        else
            let bruteSum = (if i >= 0 then x[i] else 0) + (if j >= 0 then y[j] else 0) + carry
            let carry, newDigit = if bruteSum >= 10 then 1, bruteSum - 10 else 0, bruteSum
            addCurrentDigit (i - 1) (j - 1) carry (newDigit :: xPlusY)

    addCurrentDigit (List.length x - 1) (List.length y - 1) 0 []

Here addCurrentDigit executes one step and then calls itself, passing the following indexes (i - 1 and j - 1), the carry, and the new list with the new digit at the beginning; the stop condition happens when both indexes are exhausted. We have replaced the loop with the recursive calls, and the state-changing variables with arguments that vary with each new call. Sometimes the functional style is better, sometimes the imperative style is more adequate, we have to hone our skills to use either one as better suits the scenario, and F# itself works fine with both styles.

The subtract function is pretty similar: it goes from tail to head, it also carries a value for the next step, the exact operation differs (- instead of +) and also the way we use the carry is different, but aside from that, the code is pretty similar to the one in add:

let subtract (x: int list) (y: int list) =
    let rec subtractCurrentDigit i j carry xMinusY =
        if i < 0 && j < 0 then
            if List.head xMinusY = 0 then List.tail xMinusY else xMinusY
        else
            let bruteSubstraction = (if i >= 0 then x[i] else 0) - (if j >= 0 then y[j] else 0) - carry
            let carry, newDigit = if bruteSubstraction < 0 then 1, bruteSubstraction + 10 else 0, bruteSubstraction
            subtractCurrentDigit (i - 1) (j - 1) carry (newDigit :: xMinusY)

    subtractCurrentDigit (List.length x - 1) (List.length y - 1) 0 []

All we have left to check is the leftShift function, an essential part of the Karatsuba algorithm is to multiply by a power of ten, e.g., by 10¹ or 10⁵, we can efficiently achieve this by augmenting 1 or 5 zeroes to the right of the number, and this is precisely what x leftShift m, or x <<< m, does:

let leftShift x m =
    x @ List.replicate m 0

List.replicate m 0 creates a list with m zeroes, and then we append this list to the original one (or rather we make a new list without changing the original one).

Our exploration about implementing the Karatsuba algorithm in a functional style is complete, and, leaving aside efficiency considerations, I think it holds up very well. You can check the full source code here.