1. dafis
  2. arithmoi

Commits

dafis  committed bd35806

Elaborate on overflow

  • Participants
  • Parent commits a9e7c98
  • Branches default

Comments (0)

Files changed (2)

File Math/NumberTheory/Primes/Sieve.hs

View file
  • Ignore whitespace
 -- where sieving is done, thus sieving primes up to @n@ requires
 -- @/O/(sqrt n/log n)@ space.
 module Math.NumberTheory.Primes.Sieve
-    ( primes
+    ( -- * Limitations
+      -- $limits
+      -- * Sieves and lists
+      primes
     , sieveFrom
     , PrimeSieve
     , primeSieve
     ) where
 
 import Math.NumberTheory.Primes.Sieve.Eratosthenes
+
+-- $limits
+--
+-- There are three factors limiting the range of these sieves.
+--
+-- (1) Memory
+--
+-- (2) Overflow
+--
+-- (3) The internal representation of the state
+--
+-- An Eratosthenes type sieve needs to store the primes up to the square root of
+-- the currently sieved region, thus requires @/O/(n\/log n)@ space.We store @16@ bytes
+-- of information per prime, thus a Gigabyte of memory takes you to about @1.6*10^18@.
+-- The @log@ doesn't change much in that range, so as a first approximation, doubling
+-- the storage increases the sieve range by a factor of four.
+--
+-- On a 64-bit system, this is (currently) the only limitation to be concerned with, but
+-- with more than four Terabyte of memory, the fact that the internal representation
+-- currently limits the sieve range to about @6.8*10^25@ could become relevant.
+-- Overflow in array indexing doesn't become a concern before memory and internal
+-- representation would allow to sieve past @10^37@.
+--
+-- On a 32-bit system, the internal representation imposes no additional limits,
+-- but overflow has to be reckoned with. On the one hand, the fact that arrays are
+-- 'Int'-indexed restricts the size of the prime store, on the other hand, overflow
+-- in calculating the indices to cross off multiples is possible before running out
+-- of memory. The former limits the upper bound of the monolithic 'primeSieve' to
+-- shortly above @8*10^9@, the latter limits the range of the segmented sieves to
+-- about @1.7*10^18@.

File Math/NumberTheory/Primes/Sieve/Eratosthenes.hs

View file
  • Ignore whitespace
                             ]
 
 -- | List of primes.
---   Since the sieve uses unboxed arrays, overflow occurs at some point,
---   but not before @10^6*'fromIntegral' ('maxBound' :: 'Int')@ (I forgot where exactly).
+--   Since the sieve uses unboxed arrays, overflow occurs at some point.
+--   On 64-bit systems, that point is beyond the memory limits, on
+--   32-bit systems, it is at about @1.7*10^18@.
 primes :: [Integer]
 primes = 2:3:5:concat [[vO + toPrim i | i <- [0 .. li], unsafeAt bs i]
                                 | PS vO bs <- psieveList, let (_,li) = bounds bs]