## 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 flooreddivision 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 avery large (positive or negative) number and the calculationsperformed in 'fdiv' overflow. The following definition of 'fdiv'avoids this but needs a symmetrical /MOD (quotient on top) operatorhere 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 thequotient. This works because, regardless of the choosendivision method, the rest is 0 iff the dividend is is a multiple ofthe 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.dePreusserstr 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'scomplement arithmetic and uses the technique of adding back the biasin 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 asigned 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 invertit in the case of the divisor being negative.If you don't have U/MOD, you can use any version of M/MOD because oncethe 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'scomplement negative number is represented as some bias + the numberitself.  If we want to divide negative double a by single b, thearithmetic 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 + BbHowever, there is a carry bit when we calculate B^2 + Bb.  As thiscarry is thrown away, we effectively _subtract_ B^2.  Thus the resultof the addition is            a + BbWe then divide by b:             a + Bb            -------               b  Which cancels to:             a             --- + B             b  As the division truncates downwards, the result is floor(-(a/b)) intwo'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.  Asthe carry is thrown away, we have 2FFDB.Divide 2FFDB by 3 = FFF3, which is -0D, the correct result in 16 bittwo'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.