=== 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;