I'm not *at all* close to this, but what you say sounds sensible.
What is the user-facing 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: ghc-devs On Behalf Of Sylvain Henry
| Sent: 15 November 2019 16:04
| To: ghc-devs
| 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/hsyl20-integer/libraries/ghc-
| bignum/docs/ghc-bignum.rst
|
| To summarize, we would have a single `ghc-bignum` 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 wired-in 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 integer-simple doesn't
| use the same representations for numbers as integer-gmp. But I have
| written a new pure Haskell implementation which happens to be faster
| than integer-simple (see perf results in the document linked above) and
| that uses the common representation (similar to what was used in
| integer-gmp).
|
| 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 integer-simple and integer-gmp. However integer-gmp and
| integer-simple 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
| _______________________________________________
| ghc-devs mailing list
| ghc-devs@haskell.org
| http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
