BACK |
+ , - , 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:
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