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 <[email protected]> On Behalf Of Sylvain Henry | Sent: 15 November 2019 16:04 | To: ghc-devs <[email protected]> | 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 | [email protected] | http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs _______________________________________________ ghc-devs mailing list [email protected] http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
