Question about negative Integers
Simon Peyton Jones
simonpj at microsoft.com
Fri Nov 15 16:56:53 UTC 2019
I'm not *at all* close to this, but what you say sounds sensible.
What is the userfacing change you propose? Something about the behaviour of (Bits Integer)? If so, fly it past the Core Libraries Committee, but in concrete form: I propose to change X to Y.
Simon
 Original Message
 From: ghcdevs <ghcdevsbounces at haskell.org> On Behalf Of Sylvain Henry
 Sent: 15 November 2019 16:04
 To: ghcdevs <ghcdevs at haskell.org>
 Subject: Question about negative Integers

 Hi GHC devs,

 As some of you may know, I am working on fixing several longstanding
 issues with GHC's big numbers implementation (Integer, Natural). You can
 read more about it here:
 https://gitlab.haskell.org/hsyl20/ghc/raw/hsyl20integer/libraries/ghc
 bignum/docs/ghcbignum.rst

 To summarize, we would have a single `ghcbignum` package with different
 backends (GMP, pure Haskell, etc.). The backend is chosen with a Cabal
 flag and new backends are way easier to add. All the backends use the
 same representation which allows Integer and Natural types and datacons
 to be wiredin which has a lot of nice consequences (remove some
 dependency hacks in base package, make GHC agnostic of the backend used,
 etc.).

 A major roadblock in previous attempts was that integersimple doesn't
 use the same representations for numbers as integergmp. But I have
 written a new pure Haskell implementation which happens to be faster
 than integersimple (see perf results in the document linked above) and
 that uses the common representation (similar to what was used in
 integergmp).

 I am very close to submit a merge request but there is a remaining
 question about the Bits instance for negative Integer numbers:

 We don't store big negative Integer using two's complement encoding,
 instead we use signed magnitude representation (i.e. we use constructors
 to distinguish between (big) positive or negative numbers). It's already
 true today in integersimple and integergmp. However integergmp and
 integersimple fake two's complement encoding for Bits operations. As a
 consequence, every Bits operation on negative Integers does *a lot* of
 stuff. E.g. testing a single bit with `testBit` is linear in the size of
 the number, a logical `and` between two numbers involves additions and
 subtractions, etc.

 Question is: do we need/want to keep this behavior? There is nothing in
 the report that says that Integer's Bits instance has to mimic two's
 complement encoding. What's the point of slowly accessing a fake
 representation instead of the actual one? Could we deprecate this? The
 instance isn't even coherent: popCount returns the negated numbers of 1s
 in the absolute value as it can't return an infinite value.

 Thanks,
 Sylvain
 _______________________________________________
 ghcdevs mailing list
 ghcdevs at haskell.org
 http://mail.haskell.org/cgibin/mailman/listinfo/ghcdevs
More information about the ghcdevs
mailing list