1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
|
{-# OPTIONS_GHC -Wno-type-defaults #-}
{-# OPTIONS_GHC -Wno-x-partial #-}
{-# OPTIONS_GHC -Wno-unrecognised-warning-flags #-}
module Math.NumberTheory.PrimesBench
( benchSuite
) where
import Test.Tasty.Bench
import System.Random
import Math.NumberTheory.Logarithms (integerLog2)
import Math.NumberTheory.Primes (factorise)
import Math.NumberTheory.Primes.Testing
genInteger :: Int -> Int -> Integer
genInteger salt bits
= head
. dropWhile ((< bits) . integerLog2)
. scanl (\a r -> a * 2^31 + abs r) 1
. randoms
. mkStdGen
$ salt + bits
-- | bases by Jim Sinclair, https://miller-rabin.appspot.com
fermatBases :: [Integer]
fermatBases = [2, 325, 9375, 28178, 450775, 9780504, 1795265022]
isStrongFermat :: Integer -> Bool
isStrongFermat n = all (isStrongFermatPP n) fermatBases
isFermat :: Integer -> Bool
isFermat n = all (isFermatPP n) fermatBases
comparePrimalityTests :: Int -> Benchmark
comparePrimalityTests bits = bgroup ("primality" ++ show bits)
[ bench "isPrime" $ nf (map isPrime) ns
, bench "millerRabinV 0" $ nf (map $ millerRabinV 0) ns
, bench "millerRabinV 10" $ nf (map $ millerRabinV 10) ns
, bench "millerRabinV 50" $ nf (map $ millerRabinV 50) ns
, bench "isStrongFermatPP" $ nf (map isStrongFermat) ns
, bench "isFermatPP" $ nf (map isFermat) ns
]
where
ns = take bits [genInteger 0 bits ..]
compareFactorisation :: Int -> Benchmark
compareFactorisation bits =
bench ("factorise" ++ show bits) $ nf (map factorise) ns
where
ns = take (bits `div` 10) [genInteger 0 bits ..]
benchSuite :: Benchmark
benchSuite = bgroup "Primes" $
map comparePrimalityTests [50, 100, 200, 500, 1000, 2000]
++
map compareFactorisation [50, 60, 70, 80, 90, 100]
|
