Post by thread:Arithmetic shift right

msullivan@vax.niobrara.com (Mark K Sullivan) wrote: > > I needed to divide a 2's complement number by 2 and I just thought of this > quickie arithmetic shift. Stop me if you've heard it before... Too late ;) > > rlf MyVar,W ;copy sign to carry > rrf MyVar ;shift and duplicate sign There is just one slight problem with using shifts to divide -ve numbers. To illustrate: what happens to -1 when you do this? Try this code instead: btfsc MyVar,7 incf MyVar rlf MyVar,w rrf MyVar -- Clyde Smith-Stubbs | HI-TECH Software, | Voice: +61 7 3300 5011 spam_OUTclydeTakeThisOuThitech.com.au | P.O. Box 103, Alderley, | Fax: +61 7 3300 5246 http://www.hitech.com.au | QLD, 4051, AUSTRALIA. | BBS: +61 7 3300 5235 ---------------------------------------------------------------------------- For info on the World's best C cross compilers for embedded systems, point your WWW browser at http://www.hitech.com.au, or email .....infoKILLspam@spam@hitech.com.au

In a message dated 96-05-26 05:38:43 EDT, Clyde Smith-Stubbs wrote: {Quote hidden}>msullivanKILLspamvax.niobrara.com (Mark K Sullivan) wrote: >> >> I needed to divide a 2's complement number by 2 and I just thought of this >> quickie arithmetic shift. Stop me if you've heard it before... Too late >;) >> >> rlf MyVar,W ;copy sign to carry >> rrf MyVar ;shift and duplicate sign > >There is just one slight problem with using shifts to divide -ve >numbers. To illustrate: what happens to -1 when you do this? > >Try this code instead: > > btfsc MyVar,7 > incf MyVar > rlf MyVar,w > rrf MyVar > >-- You bring up an interesting point, Clyde. It's true that Mark's routine yields -1 as the result of dividing -1 by 2. 8^( But that could be seen as the desired result. 8^). It leaves an error of 1/2, but then that's true of *every* odd number in the input. Mark's routine also has the advantage of leaving the size of the output bins the same. That is, there are *exactly* two input numbers which yield any given output number. With your scheme, a result of -40H is given *only* by an input of -80H, while a result of 0 is given by *three* inputs: -1, 0, and 1. I'm sure there are applications where either one of these algorithms is more useful than the other! Integers are fun, eh wot?? Regards... Shel Michaels .....sbmichaelsKILLspam.....aol.com http://members.aol.com/sbmichaels

msullivan@vax.niobrara.com (Mark K Sullivan) wrote: > I needed to divide a 2's complement number by 2 and I just thought of this > quickie arithmetic shift. Stop me if you've heard it before... Too late ;) > rlf MyVar,W ;copy sign to carry > rrf MyVar ;shift and duplicate sign Clyde Smith-Stubbs <EraseMEclydespam_OUTTakeThisOuTHITECH.COM.AU> writes: > There is just one slight problem with using shifts to divide -ve > numbers. To illustrate: what happens to -1 when you do this? It gets divided by two yielding -0.5. In integer representation there is no 2**-1 bit, so division by right shift truncates, effectively rounding down (toward negative infinity). -0.5 rounds to -1. Your proposed alternate code simply biases the result for negative numbers by 0.5, implementing round toward zero. It is not obvious to me that round toward zero is more "correct". I would be inclined to prefer IEEE-style round to even. If you really care about what happens to the 0.5, you should probably be using fixed-point representation. Cheers, Eric

Eric Smith <ericspam_OUTgoonsquad.spies.com> wrote: > Clyde Smith-Stubbs <@spam@clydeKILLspamHITECH.COM.AU> writes: > > There is just one slight problem with using shifts to divide -ve > > numbers. To illustrate: what happens to -1 when you do this? > > It gets divided by two yielding -0.5. > In integer representation there is no 2**-1 bit, so division by right shift > truncates, effectively rounding down (toward negative infinity). > -0.5 rounds to -1. > > Your proposed alternate code simply biases the result for negative numbers > by 0.5, implementing round toward zero. It is not obvious to me that > round toward zero is more "correct". > > I would be inclined to prefer IEEE-style round to even. > > If you really care about what happens to the 0.5, you should probably be > using fixed-point representation. Who said anything about IEEE or floating point? The numbers being dealt with here are twos-complement integers. The problem with the original code was that (-X)/2 != -(X/2) - and the code was put forward as perfoming a division by of of a twos-complement number (apart from the fact that there's no exponent here, IEEE floats are NOT stored in twos complement form - they use sign/magnitude). The point is this; if you want to do a signed right shift, then the code is fine; if you want to do a division, then it yields an incorrect result for some -ve numbers. If your application only requires signed right shift, then by all means use signed right shift; but don't promote it as a general method of doing division. Clyde -- Clyde Smith-Stubbs | HI-TECH Software, | Voice: +61 7 3300 5011 KILLspamclydeKILLspamhitech.com.au | P.O. Box 103, Alderley, | Fax: +61 7 3300 5246 http://www.hitech.com.au | QLD, 4051, AUSTRALIA. | BBS: +61 7 3300 5235 ---------------------------------------------------------------------------- For info on the World's best C cross compilers for embedded systems, point your WWW browser at http://www.hitech.com.au, or email RemoveMEinfoTakeThisOuThitech.com.au

Sbmichaels@aol.com wrote: > You bring up an interesting point, Clyde. It's true that Mark's routine > yields -1 as the result of dividing -1 by 2. 8^( But that could be seen as > the desired result. 8^). It leaves an error of 1/2, but then that's true of > *every* odd number in the input. My point was that an arithmetic shift is not equivalent to division where negative numbers are concerned - any algorithm labelled division should preserve the property that (-X)/2 == -(X/2) - and right shift does not. Looking again at the subject of this thread, it seems likely that Mark only needed a right shift, and did not intend to suggest that the code performed a division as such. But he used the term "divide" in the body of the message. Clyde -- Clyde Smith-Stubbs | HI-TECH Software, | Voice: +61 7 3300 5011 spamBeGoneclydespamBeGonehitech.com.au | P.O. Box 103, Alderley, | Fax: +61 7 3300 5246 http://www.hitech.com.au | QLD, 4051, AUSTRALIA. | BBS: +61 7 3300 5235 ---------------------------------------------------------------------------- For info on the World's best C cross compilers for embedded systems, point your WWW browser at http://www.hitech.com.au, or email TakeThisOuTinfoEraseMEspam_OUThitech.com.au

On Sun, 26 May 1996, Eric Smith wrote: > > numbers. To illustrate: what happens to -1 when you do this? > > It gets divided by two yielding -0.5. > In integer representation there is no 2**-1 bit, so division by right shift > truncates, effectively rounding down (toward negative infinity). > -0.5 rounds to -1. No. That is not truncation you're describing: what Clyde posted results in truncation (-1/2 truncated results in zero). > Your proposed alternate code simply biases the result for negative numbers > by 0.5, implementing round toward zero. It is not obvious to me that > round toward zero is more "correct". > > I would be inclined to prefer IEEE-style round to even. De gustibus non est disputandum, but having -1 / 2 give a result of -1 will be surprising to anyone who's accustomed to integer division as usually implented. > If you really care about what happens to the 0.5, you should probably be > using fixed-point representation. Of couse, this argues equally against either result. ;-)

> > My point was that an arithmetic shift is not equivalent to division where > negative numbers are concerned - any algorithm labelled division should preserve > the property that (-X)/2 == -(X/2) - and right shift does not. Why is that property any more important than (X+2)/2 == (X/2)+1 ? Or the property 0 <= X-2*(X/2) < 2? Most language specifications do not mandate usage of either the "symetric" model or "uniform model" of division. I think many, including C, mandate that X = X*(X div Y) + (X mod Y) and (X div Y)-1 < (float)(X / Y) < (X div Y)+1 for all X and Y, and (X div Y) <= (X/Y) for all (X,Y) > (0,0) but neither the round-to-zero nor round-to-lowest semantics are mandated for X<0 or Y<0. In practice, for numerical displays the round-to-zero semantics may some- times be preferable, but for graphical displays or analog output the round-to-lowest works better. much better.

This is getting a little off topic, but: "John Payson" <RemoveMEsupercatTakeThisOuTmcs.com> wrote: > division. I think many, including C, mandate that > > X = X*(X div Y) + (X mod Y) > > for all (X,Y) > (0,0) but neither the round-to-zero nor round-to-lowest > semantics are mandated for X<0 or Y<0. This is partially true; the ANSI C standard does allow that an implementation may round a negative result down, rather than towards zero, when using the / operator. This was, however, introduced solely to avoid a gross slowdown on bizarre hardware. The committee wanted to make integer division well-defined, but compromised by defining the div() and ldiv() functions, which round towards zero. See the ANSI C Rationale, section 3.3.5. I think this had best be concluded by saying that a signed right shift does implement an operation that can be labelled "division", but that most people would be surprised by the result of (-1)/2 in this case. Where a particular application can accept rounding towards negative infinity, use of a right shift for signed division may be a fast solution. Clyde -- Clyde Smith-Stubbs | HI-TECH Software, | Voice: +61 7 3300 5011 clydeEraseME.....hitech.com.au | P.O. Box 103, Alderley, | Fax: +61 7 3300 5246 http://www.hitech.com.au | QLD, 4051, AUSTRALIA. | BBS: +61 7 3300 5235 ---------------------------------------------------------------------------- For info on the World's best C cross compilers for embedded systems, point your WWW browser at http://www.hitech.com.au, or email EraseMEinfohitech.com.au

> I think this had best be concluded by saying that a signed right shift > does implement an operation that can be labelled "division", but that > most people would be surprised by the result of (-1)/2 in this case. Where a > particular application can accept rounding towards negative infinity, use > of a right shift for signed division may be a fast solution. You may prefer the round-toward-zero semantics; I for one have NEVER had a situation in which they were desirable, and have frequently had cases where I wished that the identity: ((a mod m)+b) mod m == (a+b) mod m would hold for--most notably--all 0<=a<m, -m<b<m, but unfortunately the round-to-zero semantics on many machines break this requiring me to use constructs like: a=(a+m+b) mod m rather than a=(a+b) mod m which is simpler, faster, and more logical. The only case I know of in which round-toward-zero semantics are desirable are when converting a number into a displayable representation; even there, the normal first step is to take the absolute value of a number after (optionally) output- ting a plus or minus sign; delaying any rounding until after the abs-val operation will ensure consistent behavior.