Arithmetic Shifting Considered Harmful (1976) [pdf] | Hacker News Reader

Arithmetic Shifting Considered Harmful (1976) [pdf]

dspace.mit.edu

44 pointstjalfi12 comments

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

Wikipedia has a huge list of mod implementations:

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

x86-64 clang 10.0.0 -O2 uses asr

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

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.

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.

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

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

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

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

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

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

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

Reply on news.ycombinator.com