[Haskell-cafe] Best bit LIST data structure
daniel.is.fischer at googlemail.com
Sun Oct 9 16:44:06 CEST 2011
On Sunday 09 October 2011, 15:54:14, Joachim Breitner wrote:
> Am Freitag, den 07.10.2011, 10:52 -0400 schrieb Ryan Newton:
> > What about just using the Data.Bits instance of Integer? Well,
> > presently, the setBit instance for very large integers creates a whole
> > new integer, shifts, and xors:
> > http://haskell.org/ghc/docs/latest/html/libraries/base/src/Data-Bits.h
> > tml#setBit (I don't know if it's possible to do better. From quick
> > googling GMP seems to use an array of "limbs" rather than a chunked
> > list, so maybe there's no way to treat large Integers as a list and
> > update only the front...)
> interesting idea. Should this be considered a bug in ghc? (Not that it
> cannot represent the result, but that it crashes even out of ghci):
> $ ghci
> GHCi, version 7.0.4: http://www.haskell.org/ghc/ :? for help
> Loading package ghc-prim ... linking ... done.
> Loading package integer-gmp ... linking ... done.
> Loading package base ... linking ... done.
> Prelude> :m + Data.Bits
> Prelude Data.Bits> setBit 0 (2^63-1::Int)
> gmp: overflow in mpz type
says info gmp:
`_mp_size' and `_mp_alloc' are `int', although `mp_size_t' is
usually a `long'. This is done to make the fields just 32 bits on some
64 bits systems, thereby saving a few bytes of data space but still
providing plenty of range.
So it seems to be GMP itself.
More information about the Haskell-Cafe