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.
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
ADDas the transformation function, and the
- Quantity function
FIVEas the starting value
In other words, we performed multiplication by constructing an abstract quantity function that applies function
EIGHT times to a starting value of
FIVE. (Since multiplication is commutative, we could just have easily applied function
FIVE times to a starting value of
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
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
Notice that we must also rename the internal references to
ZERO to refer to
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|
|(+)(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.
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.
ais known as the dividend
bis known as the divisor
cis 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_divitself. 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.
PAIRof values where the first is the decreasing value of the remainder, and the second is the divisor itself.
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
We do this within the definition of
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
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
In the case of
IS_LTE, we need to create a new function called
Also, I have added an internal function within
do_div_magnitudes that receives two parameters,
divisor. This is simply because
TAIL(pair) are not as meaningful as
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 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
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.
We can now test that our
DIV operator works correctly.
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.
All source code from the Mindshift blog series can be found on GitHub