# Algorithms Illuminated: Karatsuba multiplication 2/2

The second and final part of the posts explaining our functional implementation of Karatsuba fast multiplication algorithm.

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 the`multByOneDigit`

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^{1} or 10^{5}, 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.