Lesson 5
\ Lesson 5 - Numbers
\ The Forth Course
\ by Richard E. Haskell
\ Dept. of Computer Science and Engineering
\ Oakland University, Rochester, MI 48309
comment:
Lesson 5
NUMBERS
5.1 DOUBLE NUMBERS 5-2
5.2 DOUBLE COMPARISON OPERATORS 5-4
5.3 MULTIPLICATION AND DIVISION 5-5
5.4 FLOORED DIVISION 5-6
5.5 16-BIT OPERATORS 5-9
5.6 DOUBLE NUMBER MULTIPLICATION 5-11
5.7 EXERCISES 5-12
5.1 DOUBLE NUMBERS
A double number is a 32-bit integer that is stored as two 16-bit
words on the stack with the HI-word on top of the stack as follows:
___________
| HI-word | <---top of stack
|---------|
| LO-word |
|---------|
The stack picture of a double number will be indicated as
( d -- )
A double number is entered from the keyboard by including a decimal
point anywhere in the number. For example, if you type
1234.56
the integer value 123456 which is equal to the hex value 1E240
will be stored in the top two words of the stack as follows:
___________
| 0 0 0 1 | <---top of stack
|---------|
| E 2 4 0 |
|---------|
The variable DPL will contain the number of places after the decimal
point, 2 in this case.
The Forth word D. can be used to print the value of a double
number on the screen. Thus, if after entering 1234.56 you type D.
the value 123456 will be printed on the screen.
The following are some double number words:
D+ ( d d -- dsum )
Add two double numbers leaving a double sum.
DNEGATE ( d -- d )
Change the sign of a double number.
S>D ( n -- d )
Sign extend a single number to a double number.
DABS ( d -- d )
Take the absolute value of a double number.
D2* ( d -- d*2 )
32-bit shift left -- multiply d by 2.
D2/ ( d -- d/2 )
32-bit shift right -- divide d by 2.
DMIN ( d1 d2 -- d3 )
d3 is the lesser of d1 and d2.
DMAX ( d1 d2 -- d3 )
d3 is the greater of d1 and d2.
D- ( d1 d2 -- d1-d2 )
Subtract two double numbers leaving a double difference.
Note: the definition of D- is
: D- DNEGATE D+ ;
?DNEGATE ( d1 n -- d2 )
If n < 0 then DNEGATE d1.
Note: the definition of ?DNEGATE is
: ?DNEGATE ( d1 n -- d2 )
0<
IF
DNEGATE
THEN ;
5.2 DOUBLE COMPARISON OPERATORS
The following are the definitions of comparison operators for
double numbers:
: D0= ( d -- f ) \ flag is TRUE if d = 0
OR 0= ;
: D= ( d1 d2 -- f ) \ flag is TRUE if d1 = d2
D- D0= ;
: DU< ( ud1 ud2 -- f ) \ flag is TRUE if ud1 < ud2
ROT SWAP \ ud1L ud2L ud1H ud2H
2DUP U< \ ud1L ud2L ud1H ud2H f
IF \ ud1L ud2L ud1H ud2H
2DROP 2DROP TRUE \ f
ELSE
<> \ ud1L ud2L f
IF \ ud1L ud2L
2DROP FALSE \ f
ELSE
U< \ f
THEN
THEN ;
: D< ( d1 d2 -- f ) \ flag is TRUE if d1 < d2
2 PICK \ d1L d1H d2L d2H d1H
OVER = \ d1L D1H D2L D2H f
IF \ d1L D1H D2L D2H
DU< \ f
ELSE
NIP ROT DROP \ D1H D2H
< \ f
THEN ;
: D> ( di d2 -- f ) \ flag is TRUE if d1 >= d2
2SWAP
D< ;
5.3 MULTIPLICATION AND DIVISION
The basic multiplication and division operations upon which all
other multiplication and division words are based are
UM* ( un1 un2 -- ud )
UM* multiplies the unsigned 16-bit integer un1 by the
unsigned 16-bit integer un2 and returns the unsigned
32-bit product ud. This word uses the 8088/8086 MUL
instruction.
UM/MOD ( ud un -- urem uquot )
UM/MOD divides the unsigned 32-bit integer ud by the 16-bit
unsigned integer un and returns the unsigned quotient uquot
and the unsigned remainder urem. This word uses the
8088/8086 DIV instruction. If the high-word of ud is
greater than or equal to un then the quotient will not fit
in 16 bits. Under these conditions the 8088/8086 DIV
instruction would produce a "Divide by zero" trap error.
The Forth word UM/MOD checks for this case and returns a
hex value of FFFF for both the quotient and remainder if
the quotient is too large to fit in 16 bits.
The following F-PC word will multiply two signed 16-bit integers and
leave a 32-bit signed product.
: *D ( n1 n2 -- d )
2DUP XOR >R \ save sign of product
ABS SWAP ABS
UM* \ unsigned multiply
R> ?DNEGATE ; \ fix sign
The following F-PC word will divide an unsigned 32-bit integer by
a 16-bit unsigned integer and leave an unsigned 16-bit remainded
and a 32-bit unsigned quotient. This word will not have the
overflow problem of UM/MOD.
: MU/MOD ( ud un -- urem udquot )
>R 0 R@ \ udL udH 0 un
UM/MOD \ udL remH quotH
R> \ udL remH quotH un
SWAP >R \ udL remH un
UM/MOD \ remL quotL
R> ; \ remL quotL quotH
5.4 FLOORED DIVISION
The two signed division words
/MOD ( n1 n2 -- rem quot )
M/MOD ( d n1 -- rem quot )
perform floored division. Type the following four examples and
try to predict what will be displayed on the screen.
26 7 /MOD . .
-26 7 /MOD . .
26 -7 /MOD . .
-26 -7 /MOD . .
The results can be summarized as follows:
Dividend Divisor Quotient Remainder
26 7 3 5
-26 7 -4 2
26 -7 -4 -2
-26 -7 3 -5
Did you expect these results? The second and third results may
seem strange to you, but they are ok because all we need is the
divisor times the quotient plus the remainder to be equal to
the dividend. Note that
3 * 7 + 5 = 26
-4 * 7 + 2 = -26
-4 * -7 - 2 = 26
3 * -7 - 5 = -26
This is called floored division and is characterized by the sign
of the remainder being the same as the sign of the divisor.
This is not the only way to do division. In fact, the 8088/8086
IDIV instruction does NOT do floored division. In this case
the sign of the remainder is the same as the sign of the dividend
and the magnitude of the quotient is always the same.
To see this define the following code word that uses the IDIV
instruction:
comment;
PREFIX
CODE ?M/MOD
POP BX
POP DX
POP AX
IDIV BX
2PUSH
END-CODE
comment:
Now type
26 7 ?M/MOD . .
-26 7 ?M/MOD . .
26 -7 ?M/MOD . .
-26 -7 ?M/MOD . .
These new results can be summarized as follows:
Dividend Divisor Quotient Remainder
26 7 3 5
-26 7 -3 -5
26 -7 -3 5
-26 -7 3 -5
Note that in this case the divisor times the quotient plus the
remainder is still equal to the dividend. Although you might
like the looks of this version of division rather than the floored
division, the floored division has the advantage of resolving an
ambiguity around zero. To see this, try the following.
Floored division
3 4 /MOD . . 0 3
-3 4 /MOD . . -1 1
3 -4 /MOD . . -1 -1
-3 -4 /MOD . . 0 -3
Non-floored division
3 4 ?M/MOD . . 0 3
-3 4 ?M/MOD . . 0 -3
3 -4 ?M/MOD . . 0 3
-3 -4 ?M/MOD . . 0 -3
Note that the non-floored division can not tell the difference
between 3 4 ?M/MOD and 3 -4 ?M/MOD or between -3 4 ?M/MOD and
-3 -4 ?M/MOD.
Here is how M/MOD is defined:
: M/MOD ( d n -- rem quot )
?DUP \ return d if n = 0
IF \ dL dH n
DUP >R \ save n
2DUP XOR >R \ save sign
>R \ dL dH
DABS R@ ABS \ |dL dH| |n|
UM/MOD \ urem uquot
SWAP R> \ uquot urem n
?NEGATE \ uquot rem (sign=divisor)
SWAP R> \ rem uquot xor
0<
IF \ rem uquot
NEGATE \ rem quot
OVER \ rem quot rem
IF \ rem quot
1- \ floor quot toward -infinity
R@ \ rem quot n
ROT - \ quot floor.rem = n - rem
SWAP \ rem quot
THEN
THEN
R> DROP
THEN ;
/MOD could then defined as follows:
: /MOD ( n1 n2 -- rem quot )
>R S>D R>
M/MOD ;
F-PC actually defines /MOD as a code word which uses IDIV
followed by a flooring of the remainder and quotient.
5.5 16-BIT OPERATORS
The following is the way that the arithmetic operators that operate
on 16-bit numbers and leave 16-bit results could be defined.
Actually, F-PC defines many of these as equivalent code words
for speed.
: * ( n1 n2 -- n ) \ signed multiply
UM* DROP ;
Although this may seem strange, it is true that
if you simply throw away the high word of an
unsigned 32-bit product you will get the correct
16-bit signed answer. Of course, the product
must be in the range -32768 to +32767.
: / ( n1 n2 -- n ) \ signed division
/MOD NIP ;
: MOD ( n1 n2 -- rem )
/MOD DROP ;
: */MOD ( n1 n2 n3 -- rem n1*n2/n3 )
>R \ n1 n2
*D \ n1*n2 (32-bit product)
R> \ n1*n2 n3
M/MOD ; \ rem quot
Note that the quotient is equal to n1*n2/n3
where the intermediate product n1*n2 retains
32 bits.
: */ ( n1 n2 n3 -- n1*n2/n3 )
*/MOD NIP ;
Suppose you would like to compute n1*n2/n3 rounded to the nearest
integer. We can write
n1*n2/n3 = Q + R/n3
where Q is the quotient and R is the remainder. To round we add
1/2 to the fractional part of the answer. That is,
n1*n2/n3 = Q + R/n3 + 1/2
which we can write as
n1*n2/n3 = Q + (2*R + n3)/2*n3
We can then define */R to compute n1*n2/n3 rounded as follows:
comment;
: */R ( n1 n2 n3 -- n1*n2/n3 rounded )
DUP 2SWAP \ n3 n3 n1 n2
ROT \ n3 n1 n2 n3
*/MOD \ n3 R Q
-ROT 2* \ Q n3 2*R
OVER + \ Q n3 2*R+n3
SWAP 2* \ Q 2*R+n3 2*n3
/ + ;
comment:
5.6 DOUBLE NUMBER MULTIPLICATION
Sometimes it is necessary to multiply a double number (32-bits)
by a single number (16-bits) and obtain a double number result.
Of course, in general, if you multiply a 32-bit number by a
16-bit number you could get as much as a 48-bit product. However,
in many cases you will know that the result can't exceed 32-bits,
even though it will be greater than 16-bits.
Suppose that A, B, C, D, E, F and G are 16-bit numbers. Then we
can represent the multiplication of the 32-bit number A:B by the
16 bit number C as follows:
A B
----- -----
C
X -----
___________________________
D E
----- -----
G F
----- -----
___________________________
pH pL
----- -----
In this diagram, multiplying B times C gives the 32-bit result D:E.
Multiplying A times C gives the 32-bit result G:F. Adding these
two partial products, shifted by 16-bits as shown, will produce
the complete 48-bit product. However, we are going to drop the G
and limit the result to 32 bits. The low word of this product
will be pL = E and the high word will be pH = D + F. Therefore,
we can define the following word to do this multiplication.
comment;
: DUM* ( ud un -- ud )
DUP \ B A C C
ROT \ B C C A
* \ B C F
-ROT \ F B C
UM* \ F E D
ROT \ E D F
+ ; \ pL pH
comment:
5.7 EXERCISES
5.1 An imaging system uses a video camera to measure the volume of
ball bearings. The system measures the diameter of the ball
bearings in terms of pixel counts. The maximum pixel count
(corresponding to a diameter) is 256. The system is adjusted
so that 100 pixels corresponds to 1 cm. The ball bearings
measured with this device range in diameter from 0.25 to 2.5 cm.
Write a Forth word called VOLUME that will expect a diameter in
pixel counts on the stack and will leave the volume of the ball
bearing, rounded to the nearest cubic mm, on the stack.
Note: The volume of a sphere is (4/3)*pi*R**3 where R is the
radius and pi can be appoximated (to better than 7 places)
by 355/113.
Test your program with the following values of the diameter:
25 50 100 150 200 250
comment;