F#

Algorithms Illuminated in F#, the beginning

Implementing the Karatsuba fast multiplication algorithm in F#

Tim Roughgarden has a well-reputed course on algorithms, based on this course he wrote four books on the topic that are also pretty popular, and to be sure the videos are worth the watch. But the thing with most such courses and books is that they take a mostly imperative stance: an algorithm is a series of steps that change the state of variables or whole data structures, this doesn't bode well with the functional ideas of immutability and transforming functions; that got me thinking about how natural, or not, would it be to implement Tim's pseudo-code in a language like F#. I am clear that doing this will take time and effort but, on the other hand, I will have material for months, or rather quarters, of blog posts; furthermore, I am certain to refresh and learn a lot of stuff. For this series, I am assuming that you have got a basic knowledge of F# syntax, there are great resources for this, but aside from that I will try to explain most of the F# idioms and patterns that I will be using, so with that, let's get started!

The first algorithm that Tim discusses in Algorithms Illuminated, Part 1: The Basics is Karatsuba multiplication, a fast method for multiplying very large numbers (like with thousands of digits), by all means, I invite you to read Tim explanation but the gist of it is in this picture (kindly taken from the book):

Break the numbers to be multiplied in two pieces each (56, 78, 12, and 34 in the example) and solve the product in terms of operations with these smaller numbers according to this method (image also taken from the book):

As I mentioned above, it is better to go to the book (or the video) to understand why and how the algorithm works; once we get it, implementing this pseudo-code in F# is somewhat straightforward:

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

First of all, let me state that the definition and use of the +, -, and <<< operators are totally optional but it enhances the readability, e.g., the last line without the operators would be something like this: add (add (leftShift ac (n2*2)) (leftShift adbc n2)) bd, certainly harder to digest. Besides that, the F# code is almost a line-by-line translation from the pseudo-code.

For this exercise, I have chosen to represent each number as a list of decimal digits so for example 5678 is [5; 6; 7; 8], I am fully aware that most implementations of Karatsuba multiplication use binary digits in a continuous memory block, but my main focus is the readability of the algorithm implementation, so I am happily leaving the fast, heavy-duty versions to the performance experts.

The base case of the recursive karatsuba function is multiplying by one digit, e.g., 5678 x 4. We will follow the grade school method of going from the least to the most significant digit, an imperative implementation would be:

let multByOneDigit x d =
    let mutable xByd = List.empty<int>
    let mutable carry = 0
    
    for i in List.length x - 1 .. -1 .. 0 do
        let bruteProduct = x[i] * d
        let newCarry, newDigit = bruteProduct / 10, bruteProduct % 10 + carry
        xByd <- newDigit :: xByd
        carry <- newCarry

    if carry > 0 then carry :: xByd else xByd

This code proceeds from right to left multiplying each digit of x by d, successively growing the result list one digit at a time while carrying any value over 10 for the next step, for example, to multiply [5; 6; 7; 8] by 2 it first does 8*2 generating a list with just [6] and carrying 1, then it does 7*2+1 generating a new list with [5; 6] and carrying 1again, and so on.  Though more than one of my F# friends may sneer at the mutable variables and the state changes, there is nothing wrong with using imperative code in F#. But exploring a functional implementation of multiplyByOneDigit, without variables, with emphasis on functions that transform data, is worth the effort. One functional version of multByOneDigit could be:

let multByOneDigit (x: int list) d =
    let rec multCurrentDigit i carry xByd =
        if i < 0 then
            if carry > 0 then carry :: xByd else xByd
        else
            let bruteProduct = x[i]*d
            multCurrentDigit (i - 1) (bruteProduct / 10) (bruteProduct % 10 + carry :: xByd)
    
    multCurrentDigit (List.length x - 1) 0 []

This follows the exact same procedure as the previous implementation but it uses a function that processes the i-th digit, does the multiplication, and passes the carry and the new list to a new call of itself to process the next left digit, for example, to multiply [5; 6; 7; 8]by 2 it starts by calling multCurrentDigit 3 0 [], which then makes the call multCurrentDigit 2 1 [6] (2 x 8 = 16, so we keep the 6 and carry 1), then makes the call multCurrentDigit 1 1 [5; 6], and so on. If you picture the process in your head, this code processes a list from the tail to the head, does its calculation, and passes the carry and the growing result list to the next step. When you feel comfortable with the way this works, you can go one step further and express this using the List.foldback function like this:

let multByOneDigit x d =
     let lastCarry, xByd =
         List.foldBack
             (fun xi (carry, partialProduct) ->
                 let bruteProduct = xi*d
                 (bruteProduct / 10, bruteProduct % 10 + carry :: partialProduct) )
             x (0, [])
     if lastCarry > 0 then lastCarry :: xByd else xByd

To multiply [5; 6; 7; 8] by 2, List.foldback starts by calling the lambda function like so fun 8 (0, []), note that List.foldback takes just one parameter to accumulate and roll data to the next step but we trick it to pass two things by the simple means of passing a tuple, so for the next digit List.foldback does the callfun 7 (1, [6]), then fun 6 (1, [5; 6]), and so on.

If that last piece of code strikes you as alien, you are in the exact same position I was a few years ago, it took me quite a while to get used to the functional style, that is why I think F#'s ability to also accommodate imperative code is great for people adopting this new paradigm. It is not unusual that you want to process a collection (list, array, or something similar) item by item, "growing" a resulting collection in each step, in such scenarios List.fold or List.foldback are handy tools, get used to them, in any case, you can always fall back to defining a recursive function that processes one item, accumulates the result, and finally calls itself for the next item, as we did in our first functional implementation of multByOneDigit.

The next function in our implementation of Karatsuba multiplication is splitTailthat takes the list [5; 6; 7; 8] and returns two lists: [5; 6] and [7; 8], with the shiny new slicers in F# 6 we can do this in a cinch:

let splitTail x m =
    let splitPoint = List.length x - m
    x[.. splitPoint - 1], x[splitPoint ..]

Subtly, the last line returns a tuple with two lists, I have to say that more than functional this is almost declarative programming!

Now comes the time to implement the functions at the heart of Karatsuba: add, subtract, and leftShift, but this post is growing big already so let's leave it for the next entry, it will be in just a couple of days, I promise!

PD. The title image is By Cmglee - Own work, CC BY-SA 4.0, https://commons.wikimedia.org/w/index.php?curid=78011434