Mindshift: Part 19

Multiplication & Division

Having introduced the use of a NUMBER function to represent a signed integer, we've seen how to add and subtract these functions. Now we can look at how to multiply and divide them.

Multiplication

As we saw in Mindshift: Part5, multiplication is implemented as repeated addition. So using only a "naked" quantity function, we performed the multiplication 8 * 5 as follows:

  • Start with the quantity function EIGHT, and pass it
  • Function ADD as the transformation function, and the
  • Quantity function FIVE as the starting value

In other words, we performed multiplication by constructing an abstract quantity function that applies function ADD EIGHT times to a starting value of FIVE. (Since multiplication is commutative, we could just have easily applied function ADD FIVE times to a starting value of EIGHT).

Now that we are working with NUMBER functions, we still need to perform the computation shown above, but first, we must examine the sign part of the NUMBER.

Let's take our existing MULTIPLY function and rename it to indicate that it now operates on the magnitude (or absolute value) of a NUMBER, rather than the NUMBER itself. So our old MULTIPLY function becomes MULTIPLY_MAGNITUDES.

Notice that we must also rename the internal references to ADD and ZERO to refer to ADD_MAGNITUDES and ZERO_MAGNITUDE.

See Mindshift: Part 17 and Part 18 for definitions of functions ADD_MAGNITUDES and ZERO_MAGNITUDE

Now we need to take care of the signs of each operand. As before, writing out a table of sign permutations will help us see the desired result.

Sign Resulting from Multiplication
Operands Resulting Sign
(+)(n1) * (+)(n2) (+)(n1 * n2)
(+)(n1) * (-)(n2) (-)(n1 * n2)
(-)(n1) * (+)(n2) (-)(n1 * n2)
(-)(n1) * (-)(n2) (+)(n1 * n2)



First, we can see that no matter what the signs are, we will simply multiply the absolute values of the operands. Second, if the signs of both operands are the same, the result is positive and if they're different, then the result is negative.

Looking at the "Resulting Sign" column, we can see whether the resulting sign "is negative" by XORing the signs of the two operands. However, we want to know whether the sign "is positive", so we NOT the result of XORing the signs together.

Therefore, to multiply two NUMBERs all we need to do is construct a new NUMBER in which the resulting sign is the NOT(XOR) of the two operands' signs, and the magnitude is the absolute values of the two operands multiplied as before, giving:

Let's make sure this function behaves correctly:

Good, that works. Now let's look at division.

Division

Well, just as we did with multiplication, the division of two NUMBERs will use the same functionality as the division of two abstract quantity functions, and the resulting sign will be calculated just as we did above.

However, there is one very important difference, the result of the DIVISION operation is not necessarily going to be an integer - we must now account for a remainder.

Since we're doing integer division (and to keep things simple), we will represent the remainder as another integer rather than a decimal fraction.

Let's have a quick recap on how the existing DIVision operator works using "naked" quantity functions.

Recap Of How Division Works

In any division operation such as a ÷ b = c, each term has a name.

  • a is known as the dividend
  • b is known as the divisor
  • c is known as the quotient

The division computation works by counting how many times the divisor can be subtracted from the dividend until such time as the remainder becomes less than the divisor. For example, the division 13 ÷ 5 written out in pseudocode would be:

Since we have to perform an unknown number of subtraction operations, we need to use recursion. As you may recall from Mindshift: Part 12, recursion in Lambda Calculus is performed by passing the Y-Combinator a function that has been specially constructed to receive as its first parameter, a copy of itself, and as its second and subsequent parameters, any further parameters needed for the calculation being performed.

So in the original version of the DIV function, we created a function called do_div that takes three parameters:

  1. div_next - a copy of function do_div itself. This is supplied by the Y-Combinator and allows the function to identify itself without the need for any external or global name.
  2. count - this value starts at zero and counts the number of recursive calls needed to complete the division operation.
  3. pair - a PAIR of values where the first is the decreasing value of the remainder, and the second is the divisor itself.

The do_div function is passed to the Y-Combinator which generates the value of the div_next parameter (this is a partial function capable of recursion). In the case of our DIV operation, the partial function returned by the Y-Combinator requires us to supply it with two further values: the count and pair parameters.

We do this within the definition of DIV itself.

Division With NUMBERs

In the same way that we renamed the old MULTIPLY to be MULTIPLY_MAGNITUDES, we need to rename the do_div function to reflect the fact that it now works only with abstract quantity functions (a.k.a. magnitudes). So we'll call it do_div_magnitudes.

However, if we stopped after only renaming this function, it would produce nonsense results. The reason is that within do_div_magnitudes, we use other functions that have now been modified to work with NUMBERs and not abstract quantity functions. These are SUCCessor, SUBTRACT and IS_LTE.

In the case of IS_LTE, we need to create a new function called IS_MAGNITUDE_LTE.

Also, I have added an internal function within do_div_magnitudes that receives two parameters, remainder and divisor. This is simply because HEAD(pair) and TAIL(pair) are not as meaningful as remainder and divisor.

So now that function do_div_magnitudes works only with abstract quantity functions rather than NUMBERs, we can look at adjusting the definition of function DIV itself.

Previously, DIV was defined as:

So instead of passing the Y-Combinator do_div, we must now pass it do_div_magnitudes; however, we must also package the result inside a NUMBER with the correct sign.

The calculation of the sign is exactly the same as for the MULTIPLY operator; that is, we NOT(XOR) the operands' sign values together.

We must also be careful not to pass ZERO to do_div_magnitudes as the counter start value because this function is now a NUMBER and no longer an abstract quantity function.

Finally, we must extract the absolute values of the NUMBER operands and pass these to the Y-Combinator.

The next thing we must remember is that although the value coming back from DIV has been packaged inside a NUMBER function, it is in fact not really a NUMBER in the sense we have previously been using.

The first part of the NUMBER pair is still the sign, but second part is another PAIR containing the quotient and the remainder.

So we can put together some helper functions to unload these values into a JavaScript object.

We can now test that our DIV operator works correctly.

Cool!

Exponentiation?

Just in case you were wondering, I'm not going to implement exponentiation here because raising any number to the power of -n is the same as taking the nth root of that number.

This would require me to implement an nth-root algorithm in Lambda Calculus which in turn will lure me into the Turing tar-pit where, as Alan Perlis said in his 1982 article "Epigrams on Programming":

54 Beware of the Turing tar-pit in which everything is possible but nothing of interest is easy.

:-)

Chris W


All source code from the Mindshift blog series can be found on GitHub