Arithmetic Shifting Considered Harmful (1976) [pdf]

https://dspace.mit.edu/bitstream/handle/1721.1/6090/AIM-378.pdf?sequence=2&isAllowed=y

by tjalfi • 6 years ago

44 12 6 years ago

dspace.mit.edu

dang• 6 years ago

Url changed from https://apps.dtic.mil/dtic/tr/fulltext/u2/a031883.pdf to one that seems to load much faster.

saagarjha• 6 years ago

In general, trying to perform operations which truncate on negative numbers is fraught with peril, because everyone seems to do it differently and you need to look it up. Another one that tends to bite people is the modulus operator where either operand is negative: programming languages tend to differ on what the result should be. For example:

  $ echo "print(-7 % 3)" | python3
  2
  $ echo "print(-7 % -3)" | python3
  -1
  $ echo "System.out.println(-7 % 3)" | jshell -
  -1
  $ echo "System.out.println(-7 % -3)" | jshell -
  -1

0xff00ffee• 6 years ago

Wikipedia has a huge list of mod implementations:

https://en.wikipedia.org/wiki/Modulo_operation

a1369209993• 6 years ago

Dividing -1 by 2 gives a quotient of 0 and a remainder of -1 (See the DIVMOD routine if you want to check this out). But shifting -1 right by one bit gives -1. [1]

Yes, this is because asr/and rounds toward negative infinity (as it should), while your DIVMOD (also round toward -inf) routine incorrectly[0] implements QUOREM (round toward zero).

0: Well, you could say that it's rather the name that is incorrect, since I gather it's intended to implement quo/rem rather than div/mod.

BlackFingolfin• 6 years ago

There is no standard that says quo/rem or div/mod should mean one or the other. And in fact there are more than just two choices for how to implement these. See e.g. https://en.wikipedia.org/wiki/Modulo_operation

CalChris3• 6 years ago

x86-64 clang 10.0.0 -O2 uses asr

https://godbolt.org/z/2PAP5c

ajross• 6 years ago

Modern language standards are explicit about what the operations do and modern architectures all have two variants of right shift (arithmetic and logical, in x86 parlance) to handle the difference. This isn't a problem in practice for compilers in the modern world, though it remains a good warning for developers writing their own optimizations.

Really it's a note from a world we've forgotten, where "all" computer operations were unsigned and 2's complement math was a clever trick deployed only occasionally.

CalChris3• 6 years ago

It's true the 2s complement wasn't always universal but von Neumann proposed it in the EDVAC report (1945). It was the IBM 360 (1964) which really championed it. The PDP-8, 9, 10 and 11 all used 2s complement. By 1976 when this MIT AI Lab report was written, 2s complement was pretty standard.

I think this is just the MIT AI Lab tilting at windmills. They had their quirks like wanting the world to call pixels pels well after the world had decided on the former.

freshbob• 6 years ago

x >> 2 resulting in SAR is quite logical. I'm more concerned about

x / 2 resulting in the off-by-one error mentioned in the paper, if x is LLONG_MIN. LLONG_MIN / 2 = 0 in with their optimization.

https://godbolt.org/z/EtyNsR

CalChris3• 6 years ago

Doh. Sorry about that.

https://godbolt.org/z/xWmjpP

return x / 2

baz: # @baz mov rax, rdi shr rax, 63 add rax, rdi sar rax ret

Thorrez• 6 years ago

x / 2 resulting in the off-by-one error mentioned in the paper, if x is LLONG_MIN. LLONG_MIN / 2 = 0 in with their optimization.

Are you saying clang is leading to an off-by-one error? The code seems to behave correctly to me.

eqvinox• 6 years ago

Of course it does. You asked for an arithmetic right shift. What were you expecting to get???

Arithmetic Shifting Considered Harmful (1976) [pdf]

Related Stories