Arithmetic

- + - 1+ 1- 2* 2/ S>D UM* UM/MOD M* * ABS
SM/REM FM/MOD /MOD / MOD */MOD */

+ , - , 1+ and 1- should cause no problems.

2* is "1 LSHIFT" but 2/ is not the same as "1 RSHIFT" because it has to deal with negative numbers. When it shifts right, the most significant bit remains unchanged.

A useful primitive for building arithmetic words is:

M+ \ d1 u -- d2 ; add a single number to a double   TOS +TO [PSP CELL +] carry? IF
    1 +TO [PSP] THEN POP PSP TO TOS NEXT

A double numbertakes up two cells on the data stack, with its most significant half in the topmost cell. To convert a signed single number to a double:

: S>D  \ n -- d ; single to double number
    DUP 0< ;

Following the rules for two's complement numbers, the most significant cell is zero if the single number was positive, and -1 if it was negative.

eForth does all its arithmetic with nothing more than the above words, but for speed in multiplication and division you need at least two more primitives. The foundation for the Forth division and multiplication are the words

     UM*    u1 u2 -- d ; unsigned multiply to a double product
     UM/MOD d  u1 -- u2 ; unsigned divide of a double number


The basic algorithms for chips without hardware multiply and divide are similar to long multiplication or division by hand. Working in binary, it's all done with shifts and addition or subtraction. There are variants for each, and which works best for you will depend on your hardware. In the pseudo-code below:

UM*

Method 1 - Shifting Product Left

Assume a double-width register P ( Phigh, Plow) to hold the product.
    POP PSP TO W                \ the multiplicand u1
    0 TO P
    bits-per-cell TIMES
        RSHIFT W carry? IF \ low bit was a 1
        TOS +TO P THEN          \ add multiplier to product
        LSHIFT P                \ ready for next digit
    LOOP
Plow PUSH PSP Phigh TO TOS NEXT
Method 2 - Shifting Product Right POP PSP to Plow \ the multiplicand 0 TO Phigh bits-per-cell 1+ TIMES RSHIFT P carry? IF \ low bit of P was 1 TOS +TO Phigh THEN \ add multiplier LOOP Plow PUSH PSP Phigh to TOS NEXT

UM/MOD

For division by subtraction to work properly, the divisor must never be subtracted from a number more than twice as large. That is easy to arrange for in UM/MOD, since obviously the single-cell divisor must be larger than the most significant cell of the dividend, otherwise the quotient will overflow (that condition also tests for division by zero).


Method 1 - Shifting the Divisor Right
(This needs another double-width register D for the dividend)

     0 TO W                    \ will hold the quotient
     POP PSP TO Dhigh 
     POP PSP to Dlow           \ the dividend
     TOS TO Phigh  0 to Plow   \ the divisor
     bits-per-cell TIMES
       P D > IF  
         P D - TO P             
       1 +TO W THEN            \ another bit in the quotient
       W +TO W                 \ leftshift W for next digit
   LOOP
   Dlow PUSH PSP               \ remainder
   W TO TOS                    \ quotient


There are several ways to do the subtraction: you can test first and then subtract, subtract without testing and add the divisor back if the result is negative, or the faster 'non-restoring' method - instead of adding back at this step and subtracting again at the next, add back at the next step for the same result.


Method 2 - Shifting the Dividend Left
      POP PSP TO Dhigh
      POP PSP TO Dlow            \ dividend in D, divisor in TOS
      bits-per-cell TIMES
          LSHIFT D                \ 0 to lsb
          TOS Dhigh > IF
            Dhigh TOS  - TO Dhigh 
          1 +TO Dlow THEN         \ set bit in quotient
          LOOP
      Dhigh PUSH PSP              \ remainder
      Dlow TO TOS                 \ quotient


The same methods can be used for the comparison and subtraction, but now account has to be taken of the bit possibly moved out of Dhigh by the shift left.

The other multiplication and division words can be manufactured thus:

    : ?NEGATE   \ n f -- n' ; 
          0< IF NEGATE THEN ;
    : ABS   \ n -- +n ;
        DUP ?NEGATE ;
    : DNEGATE    \ d -- d' ; invert sign of double number
          INVERT >R INVERT R> 1 M+ ;
    : ?DNEGATE  \ d f -- d' ;
            0< IF DNEGATE THEN ;
    : DABS   \ d -- +d ;
          DUP ?DNEGATE ;
    : M* \ n1 n2 -- d ; signed multiply, single to double
          2DUP XOR >R   \ gives the sign of the result
          >R   ABS   R>ABS UM*   R> ?DNEGATE ;
    : * \ n1 n2 --n3 ;
          M* DROP ;
    : SM/REM   \ d n1 -- n2 n3 ; signed UM/MOD, rounding towards zero
            2DUP XOR >R   \ gives the sign of the quotient
            OVER >R       \ gives the sign of the remainder
            ABS >R DABS 
          R> UM/MOD SWAP 
          R> ?NEGATE 
          SWAP R> ?NEGATE ;
 
    : FM/MOD   \ d n1 -- n2 n3 ; signed UM/MOD, rounding towards -infinity
            DUP >R             \ save divisor
            SM/REM DUP 0< IF   \ quotient is negative?
          SWAP R> + SWAP 1+ ELSE  
          R> DROP THEN ;

The following division operators can use either SM/REM or FM/MOD. (Earlier Forths rounded to zero). ANS provides the two primitives so that operators can be defined where rounding is important.


    : /MOD      \ n1 n2 -- n3 n4 ; n3=remainder n4=quotient
          >R S>D R> FM/MOD ;
    : /         \ n1 n2 -- n3 ; signed divide
          /MOD NIP  ;
    : MOD       \ n1 n2 -- n3 ; n1 modulo n2
          /MOD DROP ;
    : */MOD     \ n1 n2 n3 -- remainder and quotient from n1*n2/n3
          >R M* R>   FM/MOD ;
    : */        \ n1 n2 n3 -- ; n1*n2/n3 
          */MOD NIP ; 

UD/MOD UD*

These words are not part of the Core, but are needed to implement numeric conversion, and should give a feel for how other multi-precision words can be constructed.


    : UD/MOD   \ ud1 u2 -- u3 ud4 ; single remainder, double quotient
            >R 0 R@ U/MOD        \ remainder and quotient of top half
            ROT ROT              \ bottom half, remainder
            R> UM/MOD ROT  ;     \ bring quotient of top half to top
    

    : UD*  \ ud1 u2 -- ud3 ; unsigned multiply
            DUP >R UM*     \ multiply top half
            DROP           \ if not zero, this is an overflow
          SWAP R> UM*      \ multiply bottom half
            ROT + ;        \ add product of top half