Floored division: How?

Showing 1-3 of 3 messages
Floored division: How? Neal Bridges 7/27/94 10:15 PM

Can anyone provide an example of how to perform floored
division on a system with only symmetrical division operators?

Floored division: How? Ulrich Hoffmann 7/28/94 2:06 AM
In <317eth$t...@relay.tor.hookup.net> nbri...@noc.hookup.net (Neal Bridges) writes:

>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

Floored division: How? Andrew Haley 8/2/94 2:47 AM
  Path: lyra.csx.cam.ac.uk!doc.ic.ac.uk!aixssc.uk.ibm.com!ibm.de!Munich.Germany.EU.net!Germany.EU.net!EU.net!howland.reston.ans.net!usc!hookup!noc!nbridges
   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.