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;