module Math.NumberTheory.UniqueFactorisation
( Prime
, UniqueFactorisation(..)
) where
import Control.Arrow
import Data.Coerce
#if MIN_VERSION_base(4,8,0)
#else
import Data.Word
#endif
import Math.NumberTheory.Primes.Factorisation as F (factorise')
import Math.NumberTheory.GaussianIntegers as G
import Numeric.Natural
newtype SmallPrime = SmallPrime { _unSmallPrime :: Word }
deriving (Eq, Ord, Show)
newtype BigPrime = BigPrime { _unBigPrime :: Natural }
deriving (Eq, Ord, Show)
type family Prime (f :: *) :: *
type instance Prime Int = SmallPrime
type instance Prime Word = SmallPrime
type instance Prime Integer = BigPrime
type instance Prime Natural = BigPrime
type instance Prime G.GaussianInteger = GaussianPrime
class UniqueFactorisation a where
unPrime :: Prime a -> a
factorise :: a -> [(Prime a, Word)]
instance UniqueFactorisation Int where
unPrime = coerce wordToInt
factorise m' = if m <= 1
then []
else map (coerce integerToWord *** intToWord) . F.factorise' . intToInteger $ m
where
m = abs m'
instance UniqueFactorisation Word where
unPrime = coerce
factorise m = if m <= 1
then []
else map (coerce integerToWord *** intToWord) . F.factorise' . wordToInteger $ m
instance UniqueFactorisation Integer where
unPrime = coerce naturalToInteger
factorise m' = if m <= 1
then []
else map (coerce integerToNatural *** intToWord) . F.factorise' $ m
where
m = abs m'
instance UniqueFactorisation Natural where
unPrime = coerce
factorise m = if m <= 1
then []
else map (coerce integerToNatural *** intToWord) . F.factorise' . naturalToInteger $ m
newtype GaussianPrime = GaussianPrime { _unGaussianPrime :: G.GaussianInteger }
deriving (Eq, Show)
instance UniqueFactorisation G.GaussianInteger where
unPrime = coerce
factorise 0 = []
factorise g = map (coerce *** intToWord) $ filter (\(h, _) -> abs h /= 1) $ G.factorise g
wordToInt :: Word -> Int
wordToInt = fromIntegral
wordToInteger :: Word -> Integer
wordToInteger = fromIntegral
intToWord :: Int -> Word
intToWord = fromIntegral
intToInteger :: Int -> Integer
intToInteger = fromIntegral
naturalToInteger :: Natural -> Integer
naturalToInteger = fromIntegral
integerToNatural :: Integer -> Natural
integerToNatural = fromIntegral
integerToWord :: Integer -> Word
integerToWord = fromIntegral