# 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 `XOR`

ing the signs of the two operands. However, we want to know whether the sign "is positive", so we `NOT`

the result of `XOR`

ing the signs together.

Therefore, to multiply two `NUMBER`

s 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 `NUMBER`

s 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 `DIV`

ision 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:

`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.`count`

- this value starts at zero and counts the number of recursive calls needed to complete the division operation.`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 `NUMBER`

s

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 `NUMBER`

s and not abstract quantity functions. These are `SUCC`

essor, `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 `NUMBER`

s, 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 `n`

th 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