Searching \ for 'Arithmetic shift right' in subject line. ()
Help us get a faster server
FAQ page: www.piclist.com/techref/index.htm?key=arithmetic+shift
Search entire site for: 'Arithmetic shift right'.

Truncated match.
'Arithmetic shift right'
1996\05\25@220246 by

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

- Mark Sullivan -
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?

btfsc   MyVar,7
incf    MyVar
rlf     MyVar,w
rrf     MyVar

--
Clyde Smith-Stubbs       | HI-TECH Software,       | Voice: +61 7 3300 5011
clydehitech.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 infohitech.com.au
In a message dated 96-05-26 05:38:43 EDT, Clyde Smith-Stubbs wrote:

{Quote hidden}

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
sbmichaelsaol.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 <clydeHITECH.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

> Clyde Smith-Stubbs <clydeHITECH.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
clydehitech.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 infohitech.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
clydehitech.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 infohitech.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.

1996\05\29@054423 by
This is getting a little off topic, but:

"John Payson" <supercatmcs.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
clydehitech.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 infohitech.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.

More... (looser matching)
- Last day of these posts
- In 1996 , 1997 only
- Today
- New search...