## BACK |

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 number*takes 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:

- <SHIFT
*register*means shift one digit left, copying the most significant byte to the carry flag (which can also be set by addition) and putting a zero in the least significant byte - SHIFT>
*register*means shift one digit right, copying the least significant byte to the carry flag and putting a zero in the most significant byte - x TIMES....LOOP means do the enclosed code x times

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

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 ;

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