Floored division: How?
Neal Bridges
Can anyone provide an example of how to perform floored
division on a system with only symmetrical division operators?
Ulrich Hoffmann
>Can anyone provide an example of how to perform floored
>division on a system with only symmetrical division operators?
Assuming symmetrical division is named 'sdiv', how about
: fdiv ( n1 n2 -- n3 )
2dup xor 0<
IF ( signs differ )
abs swap abs over + 1- swap sdiv negate EXIT THEN
( signs equal )
sdiv ;
?
10 3 sdiv . 3 10 3 fdiv . 3
11 3 sdiv . 3 11 3 fdiv . 3
12 3 sdiv . 4 12 3 fdiv . 4
-10 3 sdiv . -3 -10 3 fdiv . -4
-11 3 sdiv . -3 -11 3 fdiv . -4
-12 3 sdiv . -4 -12 3 fdiv . -4
-13 3 dvic . -4 -13 3 fdiv . -5
10 -3 sdiv . -3 10 -3 fdiv . -4
11 -3 sdiv . -3 11 -3 fdiv . -4
12 -3 sdiv . -4 12 -3 fdiv . -4
13 -3 sdiv . -4 13 -3 fdiv . -5
-10 -3 sdiv . 3 -10 -3 fdiv . 3
-11 -3 sdiv . 3 -11 -3 fdiv . 3
-12 -3 sdiv . 4 -12 -3 fdiv . 4
Please note that this version of 'fdiv' will not work if 'n1' is a
very large (positive or negative) number and the calculations
performed in 'fdiv' overflow. The following definition of 'fdiv'
avoids this but needs a symmetrical /MOD (quotient on top) operator
here called 'smoddiv':
: fdiv ( n1 n2 -- n3 )
2dup xor 0<
IF ( signs differ )
sdivmod swap IF ( with rest ) 1- THEN EXIT
THEN
( signs equal )
sdiv ;
Here the division rest is used as an indicator to adjust the
quotient. This works because, regardless of the choosen
division method, the rest is 0 iff the dividend is is a multiple of
the divisor.
Hope this helps,
Ulrich
--
Ulrich Hoffmann, Uni Kiel WWW: http://www.informatik.uni-kiel.de/~uho/
Institut f. Informatik, email: u...@informatik.uni-kiel.de
Preusserstr 1-9, D-24105 Kiel, Germany Tel: +49 431 560426 Fax: 566143
Andrew Haley
From: nbri...@noc.hookup.net (Neal Bridges)
Newsgroups: comp.lang.forth
Date: 28 Jul 1994 05:15:29 GMT
Organization: HookUp Communication Corporation, Oakville, Ontario, CANADA
Lines: 4
NNTP-Posting-Host: noc.tor.hookup.net
X-Newsreader: TIN [version 1.2 PL2]
Can anyone provide an example of how to perform floored
division on a system with only symmetrical division operators?
There's a surprisingly simple way to do this. It relies on two's
complement arithmetic and uses the technique of adding back the bias
in a negative number before performing the division:
: -M/MOD ( d +n - r q) OVER 0< IF DUP >R + R> THEN U/MOD ;
This give the correct result for the quotient and the remainder.
However, this only allows a positive divisor. To extend this to a
signed divisor, fix up the signs:
: M/ ( d n - q) DUP 0< IF NEGATE >R DNEGATE R> THEN
-M/MOD SWAP DROP ;
If you need the remainder with correct sign you'll also have to invert
it in the case of the divisor being negative.
If you don't have U/MOD, you can use any version of M/MOD because once
the fixups have been made all arguments in the division are positive.
If you can't figure out why this works, consider the fact that a two's
complement negative number is represented as some bias + the number
itself. If we want to divide negative double a by single b, the
arithmetic looks like this, where B is the bias:
a + B^2
-------
b
(Negative doubles use B^2 as the bias, rather than B.)
If we add b into the high half of a, we get:
a + B^2 + Bb
However, there is a carry bit when we calculate B^2 + Bb. As this
carry is thrown away, we effectively _subtract_ B^2. Thus the result
of the addition is
a + Bb
We then divide by b:
a + Bb
-------
b
Which cancels to:
a
--- + B
b
As the division truncates downwards, the result is floor(-(a/b)) in
two's complement notation.
As an example, consider -25 / 3 (all numbers are hex.)
On a 16 bit system the bias B is 10000.
Thus -25 as a two's complement double number is B^2 + (-25) = FFFFFFDB.
Add 3 (the divisor) into the high part of FFFFFFDB = 10002FFDB. As
the carry is thrown away, we have 2FFDB.
Divide 2FFDB by 3 = FFF3, which is -0D, the correct result in 16 bit
two's complement notation. The remainder is 2.
Finally, to quote Graham, Knuth and Patashnik:
"Beware of computer languages which use another definition [of mod]."
Andrew.