Safe Haskell | None |
---|
Prime numbers and related number theoretical stuff.
- primes :: [Integer]
- primesSimple :: [Integer]
- primesTMWE :: [Integer]
- groupIntegerFactors :: [Integer] -> [(Integer, Int)]
- integerFactorsTrialDivision :: Integer -> [Integer]
- integerLog2 :: Integer -> Integer
- ceilingLog2 :: Integer -> Integer
- isSquare :: Integer -> Bool
- integerSquareRoot :: Integer -> Integer
- ceilingSquareRoot :: Integer -> Integer
- integerSquareRoot' :: Integer -> (Integer, Integer)
- integerSquareRootNewton' :: Integer -> (Integer, Integer)
- powerMod :: Integer -> Integer -> Integer -> Integer
- millerRabinPrimalityTest :: Integer -> Integer -> Bool
List of prime numbers
primesSimple :: [Integer]Source
A relatively simple but still quite fast implementation of list of primes. By Will Ness http://www.haskell.org/pipermail/haskell-cafe/2009-November/068441.html
primesTMWE :: [Integer]Source
List of primes, using tree merge with wheel. Code by Will Ness.
Prime factorization
groupIntegerFactors :: [Integer] -> [(Integer, Int)]Source
Groups integer factors. Example: from [2,2,2,3,3,5] we produce [(2,3),(3,2),(5,1)]
integerFactorsTrialDivision :: Integer -> [Integer]Source
The naive trial division algorithm.
Integer logarithm
integerLog2 :: Integer -> IntegerSource
Largest integer k
such that 2^k
is smaller or equal to n
ceilingLog2 :: Integer -> IntegerSource
Smallest integer k
such that 2^k
is larger or equal to n
Integer square root
integerSquareRoot :: Integer -> IntegerSource
Integer square root (largest integer whose square is smaller or equal to the input) using Newton's method, with a faster (for large numbers) inital guess based on bit shifts.
ceilingSquareRoot :: Integer -> IntegerSource
Smallest integer whose square is larger or equal to the input
integerSquareRoot' :: Integer -> (Integer, Integer)Source
We also return the excess residue; that is
(a,r) = integerSquareRoot' n
means that
a*a + r = n a*a <= n < (a+1)*(a+1)
integerSquareRootNewton' :: Integer -> (Integer, Integer)Source
Newton's method without an initial guess. For very small numbers (<10^10) it is somewhat faster than the above version.
Modulo m
arithmetic
powerMod :: Integer -> Integer -> Integer -> IntegerSource
Efficient powers modulo m.
powerMod a k m == (a^k) `mod` m
Prime testing
millerRabinPrimalityTest :: Integer -> Integer -> BoolSource
Miller-Rabin Primality Test (taken from Haskell wiki).
We test the primality of the first argument n
by using the second argument a
as a candidate witness.
If it returs False
, then n
is composite. If it returns True
, then n
is either prime or composite.
A random choice between 2
and (n-2)
is a good choice for a
.