FactorisationTests.hs

-- |
-- Module:      Math.NumberTheory.Primes.FactorisationTests
-- Copyright:   (c) 2017 Andrew Lelechenko
-- Licence:     MIT
-- Maintainer:  Andrew Lelechenko <andrew.lelechenko@gmail.com>
--
-- Tests for Math.NumberTheory.Primes.Factorisation
--

{-# OPTIONS_GHC -fno-warn-type-defaults #-}

module Math.NumberTheory.Primes.FactorisationTests
  ( testSuite
  ) where

import Test.Tasty
import Test.Tasty.HUnit

import Control.Arrow
import Control.Monad (zipWithM_)
import Data.List (nub, sort)
import Data.Maybe

import Math.NumberTheory.Primes
import Math.NumberTheory.TestUtils

specialCases :: [(Integer, [(Integer, Word)])]
specialCases =
  [ (35,[(5,1),(7,1)])
  , (75,[(3,1),(5,2)])
  , (65521^2,[(65521,2)])
  , (65537^2,[(65537,2)])
  , (2147483647, [(2147483647, 1)])
  , (4294967291, [(4294967291, 1)])
  , (19000000000000000001, [(19000000000000000001, 1)])
  , (3 * 5^2 * 7^21, [(3,1), (5,2), (7, 21)])
  , (9223372036854775783, [(9223372036854775783, 1)])
  , (18446744073709551557, [(18446744073709551557, 1)])
  , (4181339589500970917,[(15034813,1),(278110515209,1)])
  , (4181339589500970918,[(2,1),(3,2),(7,1),(2595773,1),(12784336241,1)])
  , (2227144715990344929,[(3,1),(317,1),(17381911,1),(134731889,1)])
  , (10489674846272137811130167281,[(1312601,1),(9555017,1),(836368815445393,1)])
  , (10489674846272137811130167282,[(2,1),(17,1),(577,1),(3863,1),(179347163,1),(771770327021,1)])
  , (10489674846272137811130167283,[(3,1),(7,1),(4634410717,1),(107782489838601619,1)])
  , (10489674846272137811130167287,[(4122913189601,1),(2544238591472087,1)])
  , (6293073306208101456461600748,[(2,2),(3,1),(1613,1),(69973339,1),(4646378436563447,1)])
  , (6293073306208101456461600749,[(7,1),(103,1),(4726591,1),(1846628365511484259,1)])
  , (6293073306208101456461600750,[(2,1),(5,3),(239,1),(34422804769,1),(3059698456333,1)])
  , (6293073306208101456461600751,[(3,1),(13523,1),(1032679,1),(150211485989006401,1)])
  , (6293073306208101456461600753,[(19391,1),(372473053129,1),(871300023127,1)])
  , (6293073306208101456461600754,[(2,1),(3,2),(11,1),(13,1),(71,1),(2311,1),(22859,1),(7798621,1),(83583569,1)])
  , (11999991291828813663324577057,[(14381453,1),(10088205181,1),(82711187849,1)])
  , (11999991291828813663324577062,[(2,1),(3,1),(7,1),(3769,1),(634819511,1),(119413997449529,1)])
  , (16757651897802863152387219654541878160,[(2,4),(5,1),(12323,1),(1424513,1),(6205871923,1),(1922815011093901,1)])
  , (16757651897802863152387219654541878162,[(2,1),(29,1),(78173,1),(401529283,1),(1995634649,1),(4612433663779,1)])
  , (16757651897802863152387219654541878163,[(11,1),(31,1),(112160981904206269,1),(438144115295608147,1)])
  -- , (16757651897802863152387219654541878166,[(2,1),(23,1),(277,1),(505353699591289,1),(2602436338718275457,1)])
  , ((10 ^ 80 - 1) `div` 9, [(11,1),(17,1),(41,1),(73,1),(101,1),(137,1),(271,1),(3541,1),(9091,1),(27961,1),
                             (1676321,1),(5070721,1),(5882353,1),(5964848081,1),(19721061166646717498359681,1)])
  , (623506907396924300595652906937, [(300137,1),(825131,2),(1746779,2)])
  , (626472835738582668418814215862, [(2,1),(150211,1),(11746151,2),(122939,2)])
  , (638396704483535474833679624037, [(3,1),(11,2),(100519,1),(104281,2),(1268419,2)])
  ]

lazyCases :: [(Integer, [(Integer, Word)])]
lazyCases =
  [ ( 14145130711
    * 10000000000000000000000000000000000000121
    * 100000000000000000000000000000000000000000000000447
    , [(14145130711, 1)]
    )
  ]

shortenNumber :: Integer -> String
shortenNumber n
  | l <= 10 = xs
  | otherwise = take 5 xs ++ "..." ++ drop (l - 5) xs
  where
    xs = show n
    l = length xs

factoriseProperty1 :: Assertion
factoriseProperty1 = assertEqual "0" [] (factorise (1 :: Int))

factoriseProperty2 :: Positive Integer -> Bool
factoriseProperty2 (Positive n) = factorise n == factorise (negate n)

factoriseProperty3 :: Positive Integer -> Bool
factoriseProperty3 (Positive n) = all (isJust . isPrime . unPrime . fst) (factorise n)

factoriseProperty4 :: Positive Integer -> Bool
factoriseProperty4 (Positive n) = sort bases == nub (sort bases)
  where
    bases = map fst $ factorise n

factoriseProperty5 :: Positive Integer -> Bool
factoriseProperty5 (Positive n) = product (map (\(p, k) -> unPrime p ^ k) (factorise n)) == n

factoriseProperty6 :: (Integer, [(Integer, Word)]) -> Assertion
factoriseProperty6 (n, fs) = assertEqual (show n) (sort fs) (sort $ map (first unPrime) $ factorise n)

factoriseProperty7 :: (Integer, [(Integer, Word)]) -> Assertion
factoriseProperty7 (n, fs) = zipWithM_ (assertEqual (show n)) fs (map (first unPrime) $ factorise n)

testSuite :: TestTree
testSuite = testGroup "Factorisation"
  [ testGroup "factorise" $
    [ testCase          "0"                              factoriseProperty1
    , testSmallAndQuick "negate"                         factoriseProperty2
    , testSmallAndQuick "bases are prime"                factoriseProperty3
    , testSmallAndQuick "bases are distinct"             factoriseProperty4
    , testSmallAndQuick "factorback"                     factoriseProperty5
    ] ++
    map (\x -> testCase ("special case " ++ shortenNumber (fst x)) (factoriseProperty6 x)) specialCases
    ++
    map (\x -> testCase ("laziness " ++ shortenNumber (fst x)) (factoriseProperty7 x)) lazyCases
  ]