Change output of prime sieves from [Integer] to [Word]

[Bodigrim]

Currently Eratosthenes sieves from Math.NumberTheory.Primes.Sieve.Eratosthenes output a list of Integer and operate internally on Integer and Int. This was reasonable historically, when x32 architecture was omnipresent. Nowadays it does not make much sense: Eratosthenes sieves consume far too much memory beyond 2^64 to be practical.

That said, it would be more memory efficient to use Int or Word to represent generated primes. Since primes are unsigned, Word looks good. It would be even better to use newtype wrapper Prm from Math.NumberTheory.Primes.Types, but it may be deferred to a separate patch.

Another idea to achieve better backward compatibility: sieves can be parametrised by unsigned type of offset (Word or Natural) to support rare cases, when one would like to use them beyond 2^64.

[cartazio]

would it be better to use Word64? (or is there physical memory issues that leak in?)

On Sat, Mar 10, 2018 at 8:29 AM, Bodigrim notifications@github.com wrote:

Currently Eratosthenes sieves from Math.NumberTheory.Primes. Sieve.Eratosthenes output a list of Integer and operate internally on Integer and Int. This was reasonable historically, when x32 architecture was omnipresent. Nowadays it does not make much sense: Eratosthenes sieves consume far too much memory beyond 2^64 to be practical.

That said, it would be more memory efficient to use Int or Word to represent generated primes. Since primes are unsigned, Word looks good. It would be even better to use newtype wrapper Prm from Math.NumberTheory.Primes.Types, but it may be deferred to a separate patch.

Another idea to achieve better backward compatibility: sieves can be parametrised by unsigned type of offset (Word or Natural) to support rare cases, when one would like to use them beyond 2^64.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/cartazio/arithmoi/issues/94, or mute the thread https://github.com/notifications/unsubscribe-auth/AAAQwgPYJ3F8Zlewqq86DeVVde0HVGuPks5tc9UygaJpZM4SlRt8 .

[Bodigrim]

Word64 would be fine too, I think.

[Bodigrim]

I prepared a branch, which makes primes polymorphic by result type. There is still an issue, when an output type is finite. For example, primes :: [Int8] returns an infinite list of primes modulo 256 instead of a finite list of primes between 1 and 255.