Rediscovering the Distributive Property

Over the weekend, I found myself engrossed in some coding exercises from Advent of Code, where I stumbled upon a challenge involving Binary Strings and their conversion into decimal form. The process is rather simple: you map each bit to its decimal equivalent by multiplying it by $2^n$ , where n stands for the index of the bit under consideration.

For example, the binary 1011 translates to:

$1 * 2^3 + 0 * 2^2 + 1 * 2^1 + 1 * 2^0 = 11$

Naive Implementation (Haskell)

binToDec :: String -> Int
binToDec bin = sum $ map bToInt $ zip [0 ..] $ reverse bin
  where
    bToInt :: (Int, Char) -> Int
    bToInt (idx, '1') = 2 ^ idx
    bToInt (_, '0') = 0

Code Walk-through

Here is a basic overview of the Haskell code:

The function zip [0..] $ reverse bin works by reversing the string and then assigning each character with its respective index. This is to ensure the least significant digit (LSB) gets the 0 index.
bToInt is a handy utility function that accepts a pair (index, bit). It assigns a binary bit '1' to $2^i$ and a binary bit '0' to decimal 0, since it corresponds to $0 * 2^i$ .
The map function applies the bToInt function we defined to each element of the list.
Finally, the sum function combines all the corresponding decimals by adding them together.

Here's how the evaluation for the binary number 1011 proceeds:

Reverse: ['1','0','1','1'] => ['1','1','0','1']
Zip: ['1','1','0','1'] => [(0,'1'),(1,'1'),(2,'0'),(3,'1')]
Map: [(0,'1'),(1,'1'),(2,'0'),(3,'1')] => [1, 2, 0, 8]
Sum: [1, 2, 0, 8] => 11

Sure, I was familiar with this approach, but something in the back of my mind hinted that there might be more to uncover. Earlier in my programming career, I would have likely moved on, but my intuition urged me to investigate further.

Aiming for Better

I opened a fresh tab and pasted the code snippet into ChatGPT, asking if there might be a more efficient way to execute this. To my delight, the AI responded with:

binToDec :: String -> Int
binToDec bin = foldl (\acc bit -> acc * 2 + if bit == '1' then 1 else 0) 0 bin

In Haskell, the foldl function behaves much like JavaScript's reduce function. It's a higher-order function that processes a list in a particular way. The function takes three arguments: a binary function, an initial value (usually called the accumulator), and a list. foldl applies the binary function to the accumulator and the list's first element. The result becomes the new accumulator for the next element in the list. This process repeats until the list is exhausted, at which point the final accumulator value serves as the overall result. Essentially, foldl "folds" the list from the left, using the binary function to combine elements.

If we were to evaluate 1011 with this algorithm, we'd find:

$((((0 * 2 + 1) * 2 + 0) * 2 + 1) * 2 + 1) = 11$

This matches the result from our initial implementation. However, there is a significant difference in the processes. In the first implementation, each bit is evaluated individually before the sum is calculated. In contrast, the second algorithm conducts these operations incrementally within the accumulator.

The Reasoning Behind it

My instinct told me that the second approach was better as it seamlessly sidestepped the need to reverse the binary string and associate each bit with its power of 2.

But I didn't stop there. I sought to understand why these two vastly different algorithms could yield the same results. To this end, I wanted to formally analyze them.

Bit Shifting

As we continue our exploration, it's beneficial to delve a bit deeper into binary arithmetic, specifically a pivotal concept known as bit shifting. Bit shifting is an operation in the domain of binary operations that either multiplies or divides a binary number by 2, depending on the shift direction. A shift to the left (or right) effectively multiplies (or divides) the binary number by 2. This operation is a powerful tool in bitwise arithmetic and is key to understanding why the new implementation is more efficient.

Let's illustrate this concept with a quick detour. Bear in mind that this understanding is crucial to comprehending the efficiency of the new algorithm.

-- e.g., "1011" -> "10110"
shiftLeftOneBit :: String -> String
shiftLeftOneBit bin = bin ++ "0"

-- e.g., "1011" -> "101"
shiftRightOneBit :: String -> String
shiftRightOneBit bin = init bin

In binary operations, shifting a number to the left equates to appending a "0" at the end of the number, or, alternatively, multiplying by 2. On the other hand, shifting a binary number to the right is like removing the last digit, or, equivalently, performing an integer division by 2.

The reason why this works is that, on every iteration, the accumulator doubles (effectively shifting it to the left) and increments if the bit is set (i.e.,'1'). What's important here is that the sequence of addition and multiplication doesn't matter due to the distributive property. This property states that the multiplication of a number by the sum of two numbers is equivalent to multiplying the number by each of the terms and then adding the results.

Derivation

Let's begin with the distributive property of multiplication over addition, which holds that for any numbers a, b, and c.

$a * (b + c) = a * b + a * c$

We'll use this property to explain the equivalence of the two algorithms we've explored.

Let's consider a binary number represented as a string of bits $b_n,\ b_{n-1},\ ...\ b_1,\ b_0$ .

The decimal equivalent of this binary number is calculated as:

$b_n * 2^n + b_{n-1} * 2^{n-1} + ... + b_1 * 2^1 + b_0 * 2^0$

Applying the distributive property of multiplication over addition, we can transform the above equation into the form that corresponds to the steps of the foldl algorithm:

$=((b_n * 2 + b_{n-1}) * 2 + ... + b_1) * 2 + b_0$

Now, let's substitute the actual bit values for our example binary number 1011:

$=((1 * 2 + 0) * 2 + 1) * 2 + 1$

$=((2 + 0) * 2 + 1) * 2 + 1$

$=(2 * 2 + 1) * 2 + 1$

$=(4 + 1) * 2 + 1$

$=5 * 2 + 1$

$=10 + 1$

$=11$

As you can see, the binary-to-decimal transformation using the foldl algorithm (the second method) mirrors the steps of the first method, but in a different sequence. This demonstrates that the two methods are indeed mathematically equivalent, reaffirming the power and flexibility of the distributive property of multiplication over addition. With this insight, the foldl approach is not only more efficient, but it also maintains the same mathematical validity as the more verbose first approach.

Conclusion

Through this exploration, we've seen how a simple problem like binary-to-decimal conversion can be solved in multiple ways. Furthermore, we've seen how understanding the mathematical principles underlying our algorithms can lead us to more efficient solutions. Whether we're coding in Haskell or any other language, these principles can guide us in creating better, more efficient programs.