Truncated match.
PICList
Thread
'Arithmetic shift right'
1996\05\25@220246
by
Mark K Sullivan
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 
1996\05\26@053655
by
Clyde SmithStubbs
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 SmithStubbs  HITECH 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
1996\05\26@131656
by
Shel Michaels

In a message dated 960526 05:38:43 EDT, Clyde SmithStubbs 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
1996\05\26@150248
by
Eric Smith

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 SmithStubbs <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 IEEEstyle round to even.
If you really care about what happens to the 0.5, you should probably be
using fixedpoint representation.
Cheers,
Eric
1996\05\26@165035
by
Clyde SmithStubbs

Eric Smith <ericspam_OUTgoonsquad.spies.com> wrote:
> Clyde SmithStubbs <@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 IEEEstyle round to even.
>
> If you really care about what happens to the 0.5, you should probably be
> using fixedpoint representation.
Who said anything about IEEE or floating point? The numbers being dealt with
here are twoscomplement 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 twoscomplement 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 SmithStubbs  HITECH 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
1996\05\26@165713
by
Clyde SmithStubbs

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 SmithStubbs  HITECH 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
1996\05\27@123352
by
Martin J. Maney

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 IEEEstyle 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 fixedpoint representation.
Of couse, this argues equally against either result. ;)
1996\05\29@012148
by
John Payson
>
> 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 <= X2*(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 roundtozero nor roundtolowest
semantics are mandated for X<0 or Y<0.
In practice, for numerical displays the roundtozero semantics may some
times be preferable, but for graphical displays or analog output the
roundtolowest works better.
much better.
1996\05\29@054423
by
Clyde SmithStubbs

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 roundtozero nor roundtolowest
> 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 welldefined, 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 SmithStubbs  HITECH 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
1996\05\29@113805
by
John Payson

> 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 roundtowardzero 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 formost notablyall 0<=a<m, m<b<m, but unfortunately the
roundtozero 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 roundtowardzero 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 absval
operation will ensure consistent behavior.
More... (looser matching)
 Last day of these posts
 In 1996
, 1997 only
 Today
 New search...