{-# OPTIONS_GHC -Wall #-}
{-# LANGUAGE Trustworthy #-}

{- |
Module      :  Data.Complex.Cyclotomic
Copyright   :  (c) Scott N. Walck 2012-2017
License     :  GPL-3 (see LICENSE)
Maintainer  :  Scott N. Walck <walck@lvc.edu>
Stability   :  experimental

The cyclotomic numbers are a subset of the complex numbers with
the following properties:

     1.  The cyclotomic numbers are represented exactly, enabling exact
     computations and equality comparisons.

     2.  The cyclotomic numbers contain the Gaussian rationals
     (complex numbers of the form 'p' + 'q' 'i' with 'p' and 'q' rational).
     As a consequence, the cyclotomic numbers are a dense subset of the
     complex numbers.

     3.  The cyclotomic numbers contain the square roots of all rational numbers.

     4.  The cyclotomic numbers form a field:  they are closed under addition, subtraction,
     multiplication, and division.

     5.  The cyclotomic numbers contain the sine and cosine of all rational
     multiples of pi.

     6.  The cyclotomic numbers can be thought of as the rational field extended
     with 'n'th roots of unity for arbitrarily large integers 'n'.

     Floating point numbers do not do well with equality comparison:

>(sqrt 2 + sqrt 3)^2 == 5 + 2 * sqrt 6
> -> False

     "Data.Complex.Cyclotomic" represents these numbers exactly, allowing equality comparison:

>(sqrtRat 2 + sqrtRat 3)^2 == 5 + 2 * sqrtRat 6
> -> True

     'Cyclotomic's can be exported as inexact complex numbers using the 'toComplex' function:

>e 6
> -> -e(3)^2
>real $ e 6
> -> 1/2
>imag $ e 6
> -> -1/2*e(12)^7 + 1/2*e(12)^11
>imag (e 6) == sqrtRat 3 / 2
> -> True
>toComplex $ e 6
> -> 0.5000000000000003 :+ 0.8660254037844384

     The algorithms for cyclotomic numbers are adapted from code by
     Martin Schoenert and Thomas Breuer in the GAP project <http://www.gap-system.org/>
     (in particular source files gap4r4\/src\/cyclotom.c and
     gap4r4\/lib\/cyclotom.gi).
-}

module Data.Complex.Cyclotomic
    ( Cyclotomic
    , i
    , e
    , sqrtInteger
    , sqrtRat
    , sinDeg
    , cosDeg
    , sinRev
    , cosRev
    , gaussianRat
    , polarRat
    , polarRatDeg
    , polarRatRev
    , conj
    , real
    , imag
    , isReal
    , isRat
    , isGaussianRat
    , toComplex
    , toReal
    , toRat
    , goldenRatio
    , dft
    , dftInv
    , rootsQuadEq
    , heron
    )
    where

import Data.List
    ( nub
    )
import Data.Ratio
    ( (%)
    , numerator
    , denominator
    )
import Data.Complex
    ( Complex(..)
    , realPart
    )
import qualified Data.Map as M
    ( Map
    , empty
    , singleton
    , lookup
    , keys
    , elems
    , size
    , fromList
    , toList
    , mapKeys
    , filter
    , insertWith
    , delete
    , map
    , unionWith
    , findWithDefault
    , fromListWith
    )
import Math.NumberTheory.ArithmeticFunctions
    ( runFunction
    , totientA
    , smallOmegaA
    , isNFreeA
    )
import Math.NumberTheory.Primes
    ( unPrime
    , factorise
    )

-- | A cyclotomic number.
data Cyclotomic = Cyclotomic { Cyclotomic -> Integer
order  :: Integer
                             , Cyclotomic -> Map Integer Rational
coeffs :: M.Map Integer Rational
                             } deriving (Cyclotomic -> Cyclotomic -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: Cyclotomic -> Cyclotomic -> Bool
$c/= :: Cyclotomic -> Cyclotomic -> Bool
== :: Cyclotomic -> Cyclotomic -> Bool
$c== :: Cyclotomic -> Cyclotomic -> Bool
Eq)

-- | @abs@ and @signum@ are partial functions.
--   A cyclotomic number is not guaranteed to have a cyclotomic absolute value.
--   When defined, @signum c@ is the complex number with magnitude 1 that has the same argument as c;
--   @signum c = c / abs c@.
instance Num Cyclotomic where
    + :: Cyclotomic -> Cyclotomic -> Cyclotomic
(+) = Cyclotomic -> Cyclotomic -> Cyclotomic
sumCyc
    * :: Cyclotomic -> Cyclotomic -> Cyclotomic
(*) = Cyclotomic -> Cyclotomic -> Cyclotomic
prodCyc
    (-) Cyclotomic
c1 Cyclotomic
c2 = Cyclotomic -> Cyclotomic -> Cyclotomic
sumCyc Cyclotomic
c1 (Cyclotomic -> Cyclotomic
aInvCyc Cyclotomic
c2)
    negate :: Cyclotomic -> Cyclotomic
negate = Cyclotomic -> Cyclotomic
aInvCyc
    abs :: Cyclotomic -> Cyclotomic
abs = Cyclotomic -> Cyclotomic
absVal
    signum :: Cyclotomic -> Cyclotomic
signum = Cyclotomic -> Cyclotomic
sigNum
    fromInteger :: Integer -> Cyclotomic
fromInteger Integer
0 = Cyclotomic
zeroCyc
    fromInteger Integer
n = Integer -> Map Integer Rational -> Cyclotomic
Cyclotomic Integer
1 (forall k a. k -> a -> Map k a
M.singleton Integer
0 (forall a b. (Integral a, Num b) => a -> b
fromIntegral Integer
n))

instance Fractional Cyclotomic where
    recip :: Cyclotomic -> Cyclotomic
recip = Cyclotomic -> Cyclotomic
invCyc
    fromRational :: Rational -> Cyclotomic
fromRational Rational
0 = Cyclotomic
zeroCyc
    fromRational Rational
r = Integer -> Map Integer Rational -> Cyclotomic
Cyclotomic Integer
1 (forall k a. k -> a -> Map k a
M.singleton Integer
0 Rational
r)

-- | The primitive @n@th root of unity.
--   For example, @'e'(4) = 'i'@ is the primitive 4th root of unity,
--   and 'e'(5) = exp(2*pi*i/5) is the primitive 5th root of unity.
--   In general, 'e' 'n' = exp(2*pi*i/'n').
e :: Integer -> Cyclotomic
e :: Integer -> Cyclotomic
e Integer
n
    | Integer
n forall a. Ord a => a -> a -> Bool
< Integer
1      = forall a. HasCallStack => [Char] -> a
error [Char]
"e requires a positive integer"
    | Integer
n forall a. Eq a => a -> a -> Bool
== Integer
1     = Integer -> Map Integer Rational -> Cyclotomic
Cyclotomic Integer
1 (forall k a. k -> a -> Map k a
M.singleton Integer
0 Rational
1)
    | Bool
otherwise  = Integer -> Map Integer Rational -> Cyclotomic
cyclotomic Integer
n forall a b. (a -> b) -> a -> b
$ Integer -> Map Integer Rational -> Map Integer Rational
convertToBase Integer
n (forall k a. k -> a -> Map k a
M.singleton Integer
1 Rational
1)

-- instance Show Cyclotomic where
--     show (Cyclotomic n mp)
--         | mp == M.empty  = "0"
--         | otherwise      = leadingTerm rat n ex ++ followingTerms n xs
--         where ((ex,rat):xs) = M.toList mp

instance Show Cyclotomic where
    show :: Cyclotomic -> [Char]
show (Cyclotomic Integer
n Map Integer Rational
mp)
        = case forall k a. Map k a -> [(k, a)]
M.toList Map Integer Rational
mp of
            []            -> [Char]
"0"
            ((Integer
ex,Rational
rat):[(Integer, Rational)]
xs) -> Rational -> Integer -> Integer -> [Char]
leadingTerm Rational
rat Integer
n Integer
ex forall a. [a] -> [a] -> [a]
++ Integer -> [(Integer, Rational)] -> [Char]
followingTerms Integer
n [(Integer, Rational)]
xs

showBaseExp :: Integer -> Integer -> String
showBaseExp :: Integer -> Integer -> [Char]
showBaseExp Integer
n Integer
1  = [Char]
"e(" forall a. [a] -> [a] -> [a]
++ forall a. Show a => a -> [Char]
show Integer
n forall a. [a] -> [a] -> [a]
++ [Char]
")"
showBaseExp Integer
n Integer
ex = [Char]
"e(" forall a. [a] -> [a] -> [a]
++ forall a. Show a => a -> [Char]
show Integer
n forall a. [a] -> [a] -> [a]
++ [Char]
")^" forall a. [a] -> [a] -> [a]
++ forall a. Show a => a -> [Char]
show Integer
ex

leadingTerm :: Rational -> Integer -> Integer -> String
leadingTerm :: Rational -> Integer -> Integer -> [Char]
leadingTerm Rational
r Integer
_ Integer
0 = Rational -> [Char]
showRat Rational
r
leadingTerm Rational
r Integer
n Integer
ex
    | Rational
r forall a. Eq a => a -> a -> Bool
== Rational
1     = [Char]
t
    | Rational
r forall a. Eq a => a -> a -> Bool
== (-Rational
1)  = Char
'-' forall a. a -> [a] -> [a]
: [Char]
t
    | Rational
r forall a. Ord a => a -> a -> Bool
> Rational
0      = Rational -> [Char]
showRat Rational
r forall a. [a] -> [a] -> [a]
++ [Char]
"*" forall a. [a] -> [a] -> [a]
++ [Char]
t
    | Rational
r forall a. Ord a => a -> a -> Bool
< Rational
0      = [Char]
"-" forall a. [a] -> [a] -> [a]
++ Rational -> [Char]
showRat (forall a. Num a => a -> a
abs Rational
r) forall a. [a] -> [a] -> [a]
++ [Char]
"*" forall a. [a] -> [a] -> [a]
++ [Char]
t
    | Bool
otherwise  = [Char]
""
    where t :: [Char]
t = Integer -> Integer -> [Char]
showBaseExp Integer
n Integer
ex

followingTerms :: Integer -> [(Integer,Rational)] -> String
followingTerms :: Integer -> [(Integer, Rational)] -> [Char]
followingTerms Integer
_ [] = [Char]
""
followingTerms Integer
n ((Integer
ex,Rational
rat):[(Integer, Rational)]
xs) = Rational -> Integer -> Integer -> [Char]
followingTerm Rational
rat Integer
n Integer
ex forall a. [a] -> [a] -> [a]
++ Integer -> [(Integer, Rational)] -> [Char]
followingTerms Integer
n [(Integer, Rational)]
xs

followingTerm :: Rational -> Integer -> Integer -> String
followingTerm :: Rational -> Integer -> Integer -> [Char]
followingTerm Rational
r Integer
n Integer
ex
    | Rational
r forall a. Eq a => a -> a -> Bool
== Rational
1     = [Char]
" + " forall a. [a] -> [a] -> [a]
++ [Char]
t
    | Rational
r forall a. Eq a => a -> a -> Bool
== (-Rational
1)  = [Char]
" - " forall a. [a] -> [a] -> [a]
++ [Char]
t
    | Rational
r forall a. Ord a => a -> a -> Bool
> Rational
0      = [Char]
" + " forall a. [a] -> [a] -> [a]
++ Rational -> [Char]
showRat Rational
r forall a. [a] -> [a] -> [a]
++ [Char]
"*" forall a. [a] -> [a] -> [a]
++ [Char]
t
    | Rational
r forall a. Ord a => a -> a -> Bool
< Rational
0      = [Char]
" - " forall a. [a] -> [a] -> [a]
++ Rational -> [Char]
showRat (forall a. Num a => a -> a
abs Rational
r) forall a. [a] -> [a] -> [a]
++ [Char]
"*" forall a. [a] -> [a] -> [a]
++ [Char]
t
    | Bool
otherwise  = [Char]
""
    where t :: [Char]
t = Integer -> Integer -> [Char]
showBaseExp Integer
n Integer
ex

showRat :: Rational -> String
showRat :: Rational -> [Char]
showRat Rational
r
    | Integer
d forall a. Eq a => a -> a -> Bool
== Integer
1     = forall a. Show a => a -> [Char]
show Integer
n
    | Bool
otherwise  = forall a. Show a => a -> [Char]
show Integer
n forall a. [a] -> [a] -> [a]
++ [Char]
"/" forall a. [a] -> [a] -> [a]
++ forall a. Show a => a -> [Char]
show Integer
d
    where
      n :: Integer
n = forall a. Ratio a -> a
numerator Rational
r
      d :: Integer
d = forall a. Ratio a -> a
denominator Rational
r

-- GAP function EB from gap4r4/lib/cyclotom.gi
eb :: Integer -> Cyclotomic
eb :: Integer -> Cyclotomic
eb Integer
n
    | Integer
n forall a. Ord a => a -> a -> Bool
< Integer
1           = forall a. HasCallStack => [Char] -> a
error [Char]
"eb needs a positive integer"
    | Integer
n forall a. Integral a => a -> a -> a
`mod` Integer
2 forall a. Eq a => a -> a -> Bool
/= Integer
1  = forall a. HasCallStack => [Char] -> a
error [Char]
"eb needs an odd integer"
    | Integer
n forall a. Eq a => a -> a -> Bool
== Integer
1          = Cyclotomic
zeroCyc
    | Bool
otherwise       = let en :: Cyclotomic
en = Integer -> Cyclotomic
e Integer
n
                        in forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
sum [Cyclotomic
enforall a b. (Num a, Integral b) => a -> b -> a
^(Integer
kforall a. Num a => a -> a -> a
*Integer
k forall a. Integral a => a -> a -> a
`mod` Integer
n) | Integer
k <- [Integer
1..(Integer
nforall a. Num a => a -> a -> a
-Integer
1) forall a. Integral a => a -> a -> a
`div` Integer
2]]

sqrt2 :: Cyclotomic
sqrt2 :: Cyclotomic
sqrt2 = Integer -> Cyclotomic
e Integer
8 forall a. Num a => a -> a -> a
- Integer -> Cyclotomic
e Integer
8 forall a b. (Num a, Integral b) => a -> b -> a
^ (Int
3 :: Int)

-- | The square root of an 'Integer'.
sqrtInteger :: Integer -> Cyclotomic
sqrtInteger :: Integer -> Cyclotomic
sqrtInteger Integer
n
    | Integer
n forall a. Eq a => a -> a -> Bool
== Integer
0     = Cyclotomic
zeroCyc
    | Integer
n forall a. Ord a => a -> a -> Bool
< Integer
0      = Cyclotomic
i forall a. Num a => a -> a -> a
* Integer -> Cyclotomic
sqrtPositiveInteger (-Integer
n)
    | Bool
otherwise  = Integer -> Cyclotomic
sqrtPositiveInteger Integer
n

sqrtPositiveInteger :: Integer -> Cyclotomic
sqrtPositiveInteger :: Integer -> Cyclotomic
sqrtPositiveInteger Integer
n
    | Integer
n forall a. Ord a => a -> a -> Bool
< Integer
1      = forall a. HasCallStack => [Char] -> a
error [Char]
"sqrtPositiveInteger needs a positive integer"
    | Bool
otherwise  = let factors :: [(Prime Integer, Word)]
factors = forall a. UniqueFactorisation a => a -> [(Prime a, Word)]
factorise Integer
n
                       factor :: Integer
factor = forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
product [forall a. Prime a -> a
unPrime Prime Integer
p forall a b. (Num a, Integral b) => a -> b -> a
^ (Word
m forall a. Integral a => a -> a -> a
`div` Word
2) | (Prime Integer
p, Word
m) <- [(Prime Integer, Word)]
factors]
                       nn :: Integer
nn     = forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
product [forall a. Prime a -> a
unPrime Prime Integer
p forall a b. (Num a, Integral b) => a -> b -> a
^ (Word
m forall a. Integral a => a -> a -> a
`mod` Word
2) | (Prime Integer
p, Word
m) <- [(Prime Integer, Word)]
factors]
                   in case Integer
nn forall a. Integral a => a -> a -> a
`mod` Integer
4 of
                        Integer
1 -> forall a. Num a => Integer -> a
fromInteger Integer
factor forall a. Num a => a -> a -> a
* (Cyclotomic
2 forall a. Num a => a -> a -> a
* Integer -> Cyclotomic
eb Integer
nn forall a. Num a => a -> a -> a
+ Cyclotomic
1)
                        Integer
2 -> forall a. Num a => Integer -> a
fromInteger Integer
factor forall a. Num a => a -> a -> a
* Cyclotomic
sqrt2 forall a. Num a => a -> a -> a
* Integer -> Cyclotomic
sqrtPositiveInteger (Integer
nn forall a. Integral a => a -> a -> a
`div` Integer
2)
                        Integer
3 -> forall a. Num a => Integer -> a
fromInteger Integer
factor forall a. Num a => a -> a -> a
* (-Cyclotomic
i) forall a. Num a => a -> a -> a
* (Cyclotomic
2 forall a. Num a => a -> a -> a
* Integer -> Cyclotomic
eb Integer
nn forall a. Num a => a -> a -> a
+ Cyclotomic
1)
                        Integer
_ -> forall a. Num a => Integer -> a
fromInteger Integer
factor forall a. Num a => a -> a -> a
* Cyclotomic
2 forall a. Num a => a -> a -> a
* Integer -> Cyclotomic
sqrtPositiveInteger (Integer
nn forall a. Integral a => a -> a -> a
`div` Integer
4)

-- | The square root of a 'Rational' number.
sqrtRat :: Rational -> Cyclotomic
sqrtRat :: Rational -> Cyclotomic
sqrtRat Rational
r = Rational -> Cyclotomic -> Cyclotomic
prodRatCyc (Integer
1 forall a. Integral a => a -> a -> Ratio a
% forall a. Num a => Integer -> a
fromInteger Integer
den) (Integer -> Cyclotomic
sqrtInteger (forall a. Ratio a -> a
numerator Rational
r forall a. Num a => a -> a -> a
* Integer
den))
    where
      den :: Integer
den = forall a. Ratio a -> a
denominator Rational
r

-- | The square root of -1.
i :: Cyclotomic
i :: Cyclotomic
i = Integer -> Cyclotomic
e Integer
4

-- | Make a Gaussian rational; @gaussianRat p q@ is the same as @p + q * i@.
gaussianRat :: Rational -> Rational -> Cyclotomic
gaussianRat :: Rational -> Rational -> Cyclotomic
gaussianRat Rational
p Rational
q = forall a. Fractional a => Rational -> a
fromRational Rational
p forall a. Num a => a -> a -> a
+ forall a. Fractional a => Rational -> a
fromRational Rational
q forall a. Num a => a -> a -> a
* Cyclotomic
i

-- | A complex number in polar form, with rational magnitude @r@ and rational angle @s@
--   of the form @r * exp(2*pi*i*s)@; @polarRat r s@ is the same as @r * e q ^ p@,
--   where @s = p/q@.  This function is the same as 'polarRatRev'.
polarRat :: Rational    -- ^ magnitude
         -> Rational    -- ^ angle, in revolutions
         -> Cyclotomic  -- ^ cyclotomic number
polarRat :: Rational -> Rational -> Cyclotomic
polarRat Rational
r Rational
s
    = let p :: Integer
p = forall a. Ratio a -> a
numerator Rational
s
          q :: Integer
q = forall a. Ratio a -> a
denominator Rational
s
      in case Integer
p forall a. Ord a => a -> a -> Bool
>= Integer
0 of
           Bool
True  -> forall a. Fractional a => Rational -> a
fromRational Rational
r forall a. Num a => a -> a -> a
* Integer -> Cyclotomic
e Integer
q forall a b. (Num a, Integral b) => a -> b -> a
^ Integer
p
           Bool
False -> Cyclotomic -> Cyclotomic
conj forall a b. (a -> b) -> a -> b
$ forall a. Fractional a => Rational -> a
fromRational Rational
r forall a. Num a => a -> a -> a
* Integer -> Cyclotomic
e Integer
q forall a b. (Num a, Integral b) => a -> b -> a
^ (-Integer
p)

-- | A complex number in polar form, with rational magnitude and rational angle
--   in degrees.
polarRatDeg :: Rational    -- ^ magnitude
            -> Rational    -- ^ angle, in degrees
            -> Cyclotomic  -- ^ cyclotomic number
polarRatDeg :: Rational -> Rational -> Cyclotomic
polarRatDeg Rational
r Rational
deg
    = let s :: Rational
s = Rational
deg forall a. Fractional a => a -> a -> a
/ Rational
360
          p :: Integer
p = forall a. Ratio a -> a
numerator Rational
s
          q :: Integer
q = forall a. Ratio a -> a
denominator Rational
s
      in case Integer
p forall a. Ord a => a -> a -> Bool
>= Integer
0 of
           Bool
True  -> forall a. Fractional a => Rational -> a
fromRational Rational
r forall a. Num a => a -> a -> a
* Integer -> Cyclotomic
e Integer
q forall a b. (Num a, Integral b) => a -> b -> a
^ Integer
p
           Bool
False -> Cyclotomic -> Cyclotomic
conj forall a b. (a -> b) -> a -> b
$ forall a. Fractional a => Rational -> a
fromRational Rational
r forall a. Num a => a -> a -> a
* Integer -> Cyclotomic
e Integer
q forall a b. (Num a, Integral b) => a -> b -> a
^ (-Integer
p)

-- | A complex number in polar form, with rational magnitude and rational angle
--   in revolutions.
polarRatRev :: Rational    -- ^ magnitude
            -> Rational    -- ^ angle, in revolutions
            -> Cyclotomic  -- ^ cyclotomic number
polarRatRev :: Rational -> Rational -> Cyclotomic
polarRatRev Rational
r Rational
s
    = let p :: Integer
p = forall a. Ratio a -> a
numerator Rational
s
          q :: Integer
q = forall a. Ratio a -> a
denominator Rational
s
      in case Integer
p forall a. Ord a => a -> a -> Bool
>= Integer
0 of
           Bool
True  -> forall a. Fractional a => Rational -> a
fromRational Rational
r forall a. Num a => a -> a -> a
* Integer -> Cyclotomic
e Integer
q forall a b. (Num a, Integral b) => a -> b -> a
^ Integer
p
           Bool
False -> Cyclotomic -> Cyclotomic
conj forall a b. (a -> b) -> a -> b
$ forall a. Fractional a => Rational -> a
fromRational Rational
r forall a. Num a => a -> a -> a
* Integer -> Cyclotomic
e Integer
q forall a b. (Num a, Integral b) => a -> b -> a
^ (-Integer
p)

-- | Complex conjugate.
conj :: Cyclotomic -> Cyclotomic
conj :: Cyclotomic -> Cyclotomic
conj (Cyclotomic Integer
n Map Integer Rational
mp)
    = Integer -> Map Integer Rational -> Cyclotomic
mkCyclotomic Integer
n (forall k2 k1 a. Ord k2 => (k1 -> k2) -> Map k1 a -> Map k2 a
M.mapKeys (\Integer
k -> (Integer
nforall a. Num a => a -> a -> a
-Integer
k) forall a. Integral a => a -> a -> a
`mod` Integer
n) Map Integer Rational
mp)

-- | Real part of the cyclotomic number.
real :: Cyclotomic -> Cyclotomic
real :: Cyclotomic -> Cyclotomic
real Cyclotomic
z = (Cyclotomic
z forall a. Num a => a -> a -> a
+ Cyclotomic -> Cyclotomic
conj Cyclotomic
z) forall a. Fractional a => a -> a -> a
/ Cyclotomic
2

-- | Imaginary part of the cyclotomic number.
imag :: Cyclotomic -> Cyclotomic
imag :: Cyclotomic -> Cyclotomic
imag Cyclotomic
z = (Cyclotomic
z forall a. Num a => a -> a -> a
- Cyclotomic -> Cyclotomic
conj Cyclotomic
z) forall a. Fractional a => a -> a -> a
/ (Cyclotomic
2forall a. Num a => a -> a -> a
*Cyclotomic
i)

absVal :: Cyclotomic -> Cyclotomic
absVal :: Cyclotomic -> Cyclotomic
absVal Cyclotomic
c = let modsq :: Cyclotomic
modsq = Cyclotomic
c forall a. Num a => a -> a -> a
* Cyclotomic -> Cyclotomic
conj Cyclotomic
c
           in case Cyclotomic -> Maybe Rational
toRat Cyclotomic
modsq of
                Just Rational
msq -> Rational -> Cyclotomic
sqrtRat Rational
msq
                Maybe Rational
Nothing  -> forall a. HasCallStack => [Char] -> a
error [Char]
"abs not available for this number"

sigNum :: Cyclotomic -> Cyclotomic
sigNum :: Cyclotomic -> Cyclotomic
sigNum Cyclotomic
0 = Cyclotomic
zeroCyc
sigNum Cyclotomic
c = let modsq :: Cyclotomic
modsq = Cyclotomic
c forall a. Num a => a -> a -> a
* Cyclotomic -> Cyclotomic
conj Cyclotomic
c
           in if Cyclotomic -> Bool
isRat Cyclotomic
modsq then Cyclotomic
c forall a. Fractional a => a -> a -> a
/ Cyclotomic -> Cyclotomic
absVal Cyclotomic
c
              else forall a. HasCallStack => [Char] -> a
error [Char]
"signum not available for this number"

convertToBase :: Integer -> M.Map Integer Rational -> M.Map Integer Rational
convertToBase :: Integer -> Map Integer Rational -> Map Integer Rational
convertToBase Integer
n Map Integer Rational
mp = forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (\(Integer
p,Integer
r) Map Integer Rational
m -> Integer
-> Integer
-> Integer
-> Map Integer Rational
-> Map Integer Rational
replace Integer
n Integer
p Integer
r Map Integer Rational
m) Map Integer Rational
mp (Integer -> [(Integer, Integer)]
extraneousPowers Integer
n)

removeZeros :: M.Map Integer Rational -> M.Map Integer Rational
removeZeros :: Map Integer Rational -> Map Integer Rational
removeZeros = forall a k. (a -> Bool) -> Map k a -> Map k a
M.filter (forall a. Eq a => a -> a -> Bool
/= Rational
0)

-- Corresponds to GAP implementation.
-- Expects that convertToBase has already been done.
cyclotomic :: Integer -> M.Map Integer Rational -> Cyclotomic
cyclotomic :: Integer -> Map Integer Rational -> Cyclotomic
cyclotomic Integer
ord = Cyclotomic -> Cyclotomic
tryReduce forall b c a. (b -> c) -> (a -> b) -> a -> c
. Cyclotomic -> Cyclotomic
tryRational forall b c a. (b -> c) -> (a -> b) -> a -> c
. Cyclotomic -> Cyclotomic
gcdReduce forall b c a. (b -> c) -> (a -> b) -> a -> c
. Integer -> Map Integer Rational -> Cyclotomic
Cyclotomic Integer
ord

mkCyclotomic :: Integer -> M.Map Integer Rational -> Cyclotomic
mkCyclotomic :: Integer -> Map Integer Rational -> Cyclotomic
mkCyclotomic Integer
ord = Integer -> Map Integer Rational -> Cyclotomic
cyclotomic Integer
ord forall b c a. (b -> c) -> (a -> b) -> a -> c
. Map Integer Rational -> Map Integer Rational
removeZeros forall b c a. (b -> c) -> (a -> b) -> a -> c
. Integer -> Map Integer Rational -> Map Integer Rational
convertToBase Integer
ord

-- | Step 1 of cyclotomic is gcd reduction.
gcdReduce :: Cyclotomic -> Cyclotomic
gcdReduce :: Cyclotomic -> Cyclotomic
gcdReduce cyc :: Cyclotomic
cyc@(Cyclotomic Integer
n Map Integer Rational
mp) = case Cyclotomic -> Integer
gcdCyc Cyclotomic
cyc of
                                    Integer
1 -> Cyclotomic
cyc
                                    Integer
d -> Integer -> Map Integer Rational -> Cyclotomic
Cyclotomic (Integer
n forall a. Integral a => a -> a -> a
`div` Integer
d) (forall k2 k1 a. Ord k2 => (k1 -> k2) -> Map k1 a -> Map k2 a
M.mapKeys (forall a. Integral a => a -> a -> a
`div` Integer
d) Map Integer Rational
mp)

gcdCyc :: Cyclotomic -> Integer
gcdCyc :: Cyclotomic -> Integer
gcdCyc (Cyclotomic Integer
n Map Integer Rational
mp) = [Integer] -> Integer
gcdList (Integer
nforall a. a -> [a] -> [a]
:forall k a. Map k a -> [k]
M.keys Map Integer Rational
mp)

-- | Step 2 of cyclotomic is reduction to a rational if possible.
tryRational :: Cyclotomic -> Cyclotomic
tryRational :: Cyclotomic -> Cyclotomic
tryRational Cyclotomic
c
    | Cyclotomic -> Int
lenCyc Cyclotomic
c forall a. Eq a => a -> a -> Bool
== forall a b. (Integral a, Num b) => a -> b
fromIntegral Integer
phi Bool -> Bool -> Bool
&& Bool
sqfree
        = case Cyclotomic -> Maybe Rational
equalCoefficients Cyclotomic
c of
            Maybe Rational
Nothing -> Cyclotomic
c
            Just Rational
r  -> forall a. Fractional a => Rational -> a
fromRational forall a b. (a -> b) -> a -> b
$ (-Rational
1)forall a b. (Num a, Integral b) => a -> b -> a
^(Int
nrp forall a. Integral a => a -> a -> a
`mod` Int
2)forall a. Num a => a -> a -> a
*Rational
r
    | Bool
otherwise
        = Cyclotomic
c
    where
      (Integer
phi,Int
nrp,Bool
sqfree) = Integer -> (Integer, Int, Bool)
phiNrpSqfree (Cyclotomic -> Integer
order Cyclotomic
c)

-- | Compute phi(n), the number of prime factors, and test if n is square-free.
phiNrpSqfree :: Integer -> (Integer, Int, Bool)
phiNrpSqfree :: Integer -> (Integer, Int, Bool)
phiNrpSqfree = forall n a.
UniqueFactorisation n =>
ArithmeticFunction n a -> n -> a
runFunction forall a b. (a -> b) -> a -> b
$ (,,) forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall n. Num n => ArithmeticFunction n n
totientA forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> forall a n. Num a => ArithmeticFunction n a
smallOmegaA forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> forall n. Word -> ArithmeticFunction n Bool
isNFreeA Word
2

equalCoefficients :: Cyclotomic -> Maybe Rational
equalCoefficients :: Cyclotomic -> Maybe Rational
equalCoefficients (Cyclotomic Integer
_ Map Integer Rational
mp)
    = case [Rational]
ts of
        []    -> forall a. Maybe a
Nothing
        (Rational
x:[Rational]
_) -> if forall a. Eq a => [a] -> Bool
equal [Rational]
ts then forall a. a -> Maybe a
Just Rational
x else forall a. Maybe a
Nothing
      where
        ts :: [Rational]
ts = forall k a. Map k a -> [a]
M.elems Map Integer Rational
mp

lenCyc :: Cyclotomic -> Int
lenCyc :: Cyclotomic -> Int
lenCyc (Cyclotomic Integer
_ Map Integer Rational
mp) = forall k a. Map k a -> Int
M.size forall a b. (a -> b) -> a -> b
$ Map Integer Rational -> Map Integer Rational
removeZeros Map Integer Rational
mp

-- | Step 3 of cyclotomic is base reduction
tryReduce :: Cyclotomic -> Cyclotomic
tryReduce :: Cyclotomic -> Cyclotomic
tryReduce Cyclotomic
c
    = forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr Integer -> Cyclotomic -> Cyclotomic
reduceByPrime Cyclotomic
c [Integer]
squareFreeOddFactors
      where
        squareFreeOddFactors :: [Integer]
squareFreeOddFactors = [forall a. Prime a -> a
unPrime Prime Integer
p | (Prime Integer
p, Word
m) <- forall a. UniqueFactorisation a => a -> [(Prime a, Word)]
factorise (Cyclotomic -> Integer
order Cyclotomic
c), forall a. Prime a -> a
unPrime Prime Integer
p forall a. Ord a => a -> a -> Bool
> Integer
2, Word
m forall a. Ord a => a -> a -> Bool
<= Word
1]

reduceByPrime :: Integer -> Cyclotomic -> Cyclotomic
reduceByPrime :: Integer -> Cyclotomic -> Cyclotomic
reduceByPrime Integer
p c :: Cyclotomic
c@(Cyclotomic Integer
n Map Integer Rational
_)
    = case forall (t :: * -> *) (m :: * -> *) a b.
(Traversable t, Monad m) =>
(a -> m b) -> t a -> m (t b)
mapM (\Integer
r -> Integer -> Integer -> Cyclotomic -> Maybe Rational
equalReplacements Integer
p Integer
r Cyclotomic
c) [Integer
0,Integer
p..Integer
nforall a. Num a => a -> a -> a
-Integer
p] of
        Just [Rational]
cfs -> Integer -> Map Integer Rational -> Cyclotomic
Cyclotomic (Integer
n forall a. Integral a => a -> a -> a
`div` Integer
p) forall a b. (a -> b) -> a -> b
$ Map Integer Rational -> Map Integer Rational
removeZeros forall a b. (a -> b) -> a -> b
$ forall k a. Ord k => [(k, a)] -> Map k a
M.fromList forall a b. (a -> b) -> a -> b
$ forall a b. [a] -> [b] -> [(a, b)]
zip [Integer
0..(Integer
n forall a. Integral a => a -> a -> a
`div` Integer
p)forall a. Num a => a -> a -> a
-Integer
1] (forall a b. (a -> b) -> [a] -> [b]
map forall a. Num a => a -> a
negate [Rational]
cfs)
        Maybe [Rational]
Nothing  -> Cyclotomic
c

equalReplacements :: Integer -> Integer -> Cyclotomic -> Maybe Rational
equalReplacements :: Integer -> Integer -> Cyclotomic -> Maybe Rational
equalReplacements Integer
p Integer
r (Cyclotomic Integer
n Map Integer Rational
mp)
    =  case [forall k a. Ord k => a -> k -> Map k a -> a
M.findWithDefault Rational
0 Integer
k Map Integer Rational
mp | Integer
k <- Integer -> Integer -> Integer -> [Integer]
replacements Integer
n Integer
p Integer
r] of
         [] -> forall a. HasCallStack => [Char] -> a
error [Char]
"equalReplacements generated empty list"
         (Rational
x:[Rational]
xs) | forall a. Eq a => [a] -> Bool
equal (Rational
xforall a. a -> [a] -> [a]
:[Rational]
xs) -> forall a. a -> Maybe a
Just Rational
x
         [Rational]
_ -> forall a. Maybe a
Nothing

replacements :: Integer -> Integer -> Integer -> [Integer]
replacements :: Integer -> Integer -> Integer -> [Integer]
replacements Integer
n Integer
p Integer
r = forall a. (a -> Bool) -> [a] -> [a]
takeWhile (forall a. Ord a => a -> a -> Bool
>= Integer
0) [Integer
rforall a. Num a => a -> a -> a
-Integer
s,Integer
rforall a. Num a => a -> a -> a
-Integer
2forall a. Num a => a -> a -> a
*Integer
s..] forall a. [a] -> [a] -> [a]
++ forall a. (a -> Bool) -> [a] -> [a]
takeWhile (forall a. Ord a => a -> a -> Bool
< Integer
n) [Integer
rforall a. Num a => a -> a -> a
+Integer
s,Integer
rforall a. Num a => a -> a -> a
+Integer
2forall a. Num a => a -> a -> a
*Integer
s..]
    where s :: Integer
s = Integer
n forall a. Integral a => a -> a -> a
`div` Integer
p

replace :: Integer -> Integer -> Integer -> M.Map Integer Rational -> M.Map Integer Rational
replace :: Integer
-> Integer
-> Integer
-> Map Integer Rational
-> Map Integer Rational
replace Integer
n Integer
p Integer
r Map Integer Rational
mp = case forall k a. Ord k => k -> Map k a -> Maybe a
M.lookup Integer
r Map Integer Rational
mp of
                     Maybe Rational
Nothing  -> Map Integer Rational
mp
                     Just Rational
rat -> forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (\Integer
k Map Integer Rational
m -> forall k a. Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k a
M.insertWith forall a. Num a => a -> a -> a
(+) Integer
k (-Rational
rat) Map Integer Rational
m) (forall k a. Ord k => k -> Map k a -> Map k a
M.delete Integer
r Map Integer Rational
mp) (Integer -> Integer -> Integer -> [Integer]
replacements Integer
n Integer
p Integer
r)

includeMods :: Integer -> Integer -> Integer -> [Integer]
includeMods :: Integer -> Integer -> Integer -> [Integer]
includeMods Integer
n Integer
q Integer
start = [Integer
start] forall a. [a] -> [a] -> [a]
++ forall a. (a -> Bool) -> [a] -> [a]
takeWhile (forall a. Ord a => a -> a -> Bool
>= Integer
0) [Integer
startforall a. Num a => a -> a -> a
-Integer
q,Integer
startforall a. Num a => a -> a -> a
-Integer
2forall a. Num a => a -> a -> a
*Integer
q..] forall a. [a] -> [a] -> [a]
++ forall a. (a -> Bool) -> [a] -> [a]
takeWhile (forall a. Ord a => a -> a -> Bool
< Integer
n) [Integer
startforall a. Num a => a -> a -> a
+Integer
q,Integer
startforall a. Num a => a -> a -> a
+Integer
2forall a. Num a => a -> a -> a
*Integer
q..]

removeExps :: Integer -> Integer -> Integer -> [Integer]
removeExps :: Integer -> Integer -> Integer -> [Integer]
removeExps Integer
n Integer
2 Integer
q = forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMap (Integer -> Integer -> Integer -> [Integer]
includeMods Integer
n Integer
q) forall a b. (a -> b) -> a -> b
$ forall a b. (a -> b) -> [a] -> [b]
map ((Integer
n forall a. Integral a => a -> a -> a
`div` Integer
q) forall a. Num a => a -> a -> a
*) [Integer
q forall a. Integral a => a -> a -> a
`div` Integer
2..Integer
qforall a. Num a => a -> a -> a
-Integer
1]
removeExps Integer
n Integer
p Integer
q = forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMap (Integer -> Integer -> Integer -> [Integer]
includeMods Integer
n Integer
q) forall a b. (a -> b) -> a -> b
$ forall a b. (a -> b) -> [a] -> [b]
map ((Integer
n forall a. Integral a => a -> a -> a
`div` Integer
q) forall a. Num a => a -> a -> a
*) [-Integer
m..Integer
m]
    where m :: Integer
m = (Integer
q forall a. Integral a => a -> a -> a
`div` Integer
p forall a. Num a => a -> a -> a
- Integer
1) forall a. Integral a => a -> a -> a
`div` Integer
2

pqPairs :: Integer -> [(Integer, Integer)]
pqPairs :: Integer -> [(Integer, Integer)]
pqPairs Integer
n = forall a b. (a -> b) -> [a] -> [b]
map (\(Prime Integer
p, Word
k) -> (forall a. Prime a -> a
unPrime Prime Integer
p, forall a. Prime a -> a
unPrime Prime Integer
p forall a b. (Num a, Integral b) => a -> b -> a
^ Word
k)) (forall a. UniqueFactorisation a => a -> [(Prime a, Word)]
factorise Integer
n)

extraneousPowers :: Integer -> [(Integer,Integer)]
extraneousPowers :: Integer -> [(Integer, Integer)]
extraneousPowers Integer
n
    | Integer
n forall a. Ord a => a -> a -> Bool
< Integer
1      = forall a. HasCallStack => [Char] -> a
error [Char]
"extraneousPowers needs a positive integer"
    | Bool
otherwise  = forall a. Eq a => [a] -> [a]
nub forall a b. (a -> b) -> a -> b
$ forall (t :: * -> *) a. Foldable t => t [a] -> [a]
concat [[(Integer
p,Integer
r) | Integer
r <- Integer -> Integer -> Integer -> [Integer]
removeExps Integer
n Integer
p Integer
q] | (Integer
p,Integer
q) <- Integer -> [(Integer, Integer)]
pqPairs Integer
n]

-- | Sum of two cyclotomic numbers.
sumCyc :: Cyclotomic -> Cyclotomic -> Cyclotomic
sumCyc :: Cyclotomic -> Cyclotomic -> Cyclotomic
sumCyc (Cyclotomic Integer
o1 Map Integer Rational
map1) (Cyclotomic Integer
o2 Map Integer Rational
map2)
    = let ord :: Integer
ord = forall a. Integral a => a -> a -> a
lcm Integer
o1 Integer
o2
          m1 :: Integer
m1 = Integer
ord forall a. Integral a => a -> a -> a
`div` Integer
o1
          m2 :: Integer
m2 = Integer
ord forall a. Integral a => a -> a -> a
`div` Integer
o2
          map1' :: Map Integer Rational
map1' = forall k2 k1 a. Ord k2 => (k1 -> k2) -> Map k1 a -> Map k2 a
M.mapKeys (Integer
m1forall a. Num a => a -> a -> a
*) Map Integer Rational
map1
          map2' :: Map Integer Rational
map2' = forall k2 k1 a. Ord k2 => (k1 -> k2) -> Map k1 a -> Map k2 a
M.mapKeys (Integer
m2forall a. Num a => a -> a -> a
*) Map Integer Rational
map2
      in Integer -> Map Integer Rational -> Cyclotomic
mkCyclotomic Integer
ord forall a b. (a -> b) -> a -> b
$ forall k a. Ord k => (a -> a -> a) -> Map k a -> Map k a -> Map k a
M.unionWith forall a. Num a => a -> a -> a
(+) Map Integer Rational
map1' Map Integer Rational
map2'

-- | Product of two cyclotomic numbers.
prodCyc :: Cyclotomic -> Cyclotomic -> Cyclotomic
prodCyc :: Cyclotomic -> Cyclotomic -> Cyclotomic
prodCyc (Cyclotomic Integer
o1 Map Integer Rational
map1) (Cyclotomic Integer
o2 Map Integer Rational
map2)
    = let ord :: Integer
ord = forall a. Integral a => a -> a -> a
lcm Integer
o1 Integer
o2
          m1 :: Integer
m1 = Integer
ord forall a. Integral a => a -> a -> a
`div` Integer
o1
          m2 :: Integer
m2 = Integer
ord forall a. Integral a => a -> a -> a
`div` Integer
o2
      in Integer -> Map Integer Rational -> Cyclotomic
mkCyclotomic Integer
ord forall a b. (a -> b) -> a -> b
$ forall k a. Ord k => (a -> a -> a) -> [(k, a)] -> Map k a
M.fromListWith forall a. Num a => a -> a -> a
(+)
             [((Integer
m1forall a. Num a => a -> a -> a
*Integer
e1forall a. Num a => a -> a -> a
+Integer
m2forall a. Num a => a -> a -> a
*Integer
e2) forall a. Integral a => a -> a -> a
`mod` Integer
ord,Rational
c1forall a. Num a => a -> a -> a
*Rational
c2) | (Integer
e1,Rational
c1) <- forall k a. Map k a -> [(k, a)]
M.toList Map Integer Rational
map1, (Integer
e2,Rational
c2) <- forall k a. Map k a -> [(k, a)]
M.toList Map Integer Rational
map2]

-- | Product of a rational number and a cyclotomic number.
prodRatCyc :: Rational -> Cyclotomic -> Cyclotomic
prodRatCyc :: Rational -> Cyclotomic -> Cyclotomic
prodRatCyc Rational
0 Cyclotomic
_                   = Cyclotomic
zeroCyc
prodRatCyc Rational
r (Cyclotomic Integer
ord Map Integer Rational
mp) = Integer -> Map Integer Rational -> Cyclotomic
Cyclotomic Integer
ord forall a b. (a -> b) -> a -> b
$ forall a b k. (a -> b) -> Map k a -> Map k b
M.map (Rational
rforall a. Num a => a -> a -> a
*) Map Integer Rational
mp

-- | Additive identity.
zeroCyc :: Cyclotomic
zeroCyc :: Cyclotomic
zeroCyc = Integer -> Map Integer Rational -> Cyclotomic
Cyclotomic Integer
1 forall k a. Map k a
M.empty

-- | Additive inverse.
aInvCyc :: Cyclotomic -> Cyclotomic
aInvCyc :: Cyclotomic -> Cyclotomic
aInvCyc = Rational -> Cyclotomic -> Cyclotomic
prodRatCyc (-Rational
1)

multiplyExponents :: Integer -> Cyclotomic -> Cyclotomic
multiplyExponents :: Integer -> Cyclotomic -> Cyclotomic
multiplyExponents Integer
j (Cyclotomic Integer
n Map Integer Rational
mp)
    | forall a. Integral a => a -> a -> a
gcd Integer
j Integer
n forall a. Eq a => a -> a -> Bool
/= Integer
1  = forall a. HasCallStack => [Char] -> a
error [Char]
"multiplyExponents needs gcd == 1"
    | Bool
otherwise     = Integer -> Map Integer Rational -> Cyclotomic
mkCyclotomic Integer
n (forall k2 k1 a. Ord k2 => (k1 -> k2) -> Map k1 a -> Map k2 a
M.mapKeys (\Integer
k -> Integer
jforall a. Num a => a -> a -> a
*Integer
k forall a. Integral a => a -> a -> a
`mod` Integer
n) Map Integer Rational
mp)

productOfGaloisConjugates :: Cyclotomic -> Cyclotomic
productOfGaloisConjugates :: Cyclotomic -> Cyclotomic
productOfGaloisConjugates Cyclotomic
c
    = forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
product [Integer -> Cyclotomic -> Cyclotomic
multiplyExponents Integer
j Cyclotomic
c | Integer
j <- [Integer
2..Integer
ord], forall a. Integral a => a -> a -> a
gcd Integer
j Integer
ord forall a. Eq a => a -> a -> Bool
== Integer
1]
      where
        ord :: Integer
ord = Cyclotomic -> Integer
order Cyclotomic
c

-- | Multiplicative inverse.
invCyc :: Cyclotomic -> Cyclotomic
invCyc :: Cyclotomic -> Cyclotomic
invCyc Cyclotomic
z = case Cyclotomic -> Maybe Rational
toRat (Cyclotomic
z forall a. Num a => a -> a -> a
* Cyclotomic
prod) of
             Just Rational
r  -> Rational -> Cyclotomic -> Cyclotomic
prodRatCyc (Rational
1 forall a. Fractional a => a -> a -> a
/ Rational
r) Cyclotomic
prod
             Maybe Rational
Nothing -> forall a. HasCallStack => [Char] -> a
error [Char]
"invCyc:  product of Galois conjugates not rational; this is a bug, please inform package maintainer"
    where
      prod :: Cyclotomic
prod = Cyclotomic -> Cyclotomic
productOfGaloisConjugates Cyclotomic
z

-- | Is the cyclotomic a real number?
isReal :: Cyclotomic -> Bool
isReal :: Cyclotomic -> Bool
isReal Cyclotomic
c = Cyclotomic
c forall a. Eq a => a -> a -> Bool
== Cyclotomic -> Cyclotomic
conj Cyclotomic
c

-- | Is the cyclotomic a rational?
isRat :: Cyclotomic -> Bool
isRat :: Cyclotomic -> Bool
isRat (Cyclotomic Integer
1 Map Integer Rational
_) = Bool
True
isRat Cyclotomic
_                = Bool
False

-- | Is the cyclotomic a Gaussian rational?
isGaussianRat :: Cyclotomic -> Bool
isGaussianRat :: Cyclotomic -> Bool
isGaussianRat Cyclotomic
c = Cyclotomic -> Bool
isRat (Cyclotomic -> Cyclotomic
real Cyclotomic
c) Bool -> Bool -> Bool
&& Cyclotomic -> Bool
isRat (Cyclotomic -> Cyclotomic
imag Cyclotomic
c)

-- | Export as an inexact complex number.
toComplex :: RealFloat a => Cyclotomic -> Complex a
toComplex :: forall a. RealFloat a => Cyclotomic -> Complex a
toComplex Cyclotomic
c = forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
sum [forall a. Fractional a => Rational -> a
fromRational Rational
r forall a. Num a => a -> a -> a
* Complex a
enforall a b. (Num a, Integral b) => a -> b -> a
^Integer
p | (Integer
p,Rational
r) <- forall k a. Map k a -> [(k, a)]
M.toList (Cyclotomic -> Map Integer Rational
coeffs Cyclotomic
c)]
    where en :: Complex a
en = forall a. Floating a => a -> a
exp (a
0 forall a. a -> a -> Complex a
:+ a
2forall a. Num a => a -> a -> a
*forall a. Floating a => a
piforall a. Fractional a => a -> a -> a
/a
n)
          n :: a
n = forall a b. (Integral a, Num b) => a -> b
fromIntegral (Cyclotomic -> Integer
order Cyclotomic
c)

-- | Export as an inexact real number if possible.
toReal :: RealFloat a => Cyclotomic -> Maybe a
toReal :: forall a. RealFloat a => Cyclotomic -> Maybe a
toReal Cyclotomic
c
    | Cyclotomic -> Bool
isReal Cyclotomic
c   = forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$ forall a. Complex a -> a
realPart (forall a. RealFloat a => Cyclotomic -> Complex a
toComplex Cyclotomic
c)
    | Bool
otherwise  = forall a. Maybe a
Nothing

-- | Return an exact rational number if possible.
toRat :: Cyclotomic -> Maybe Rational
toRat :: Cyclotomic -> Maybe Rational
toRat (Cyclotomic Integer
1 Map Integer Rational
mp)
    | Map Integer Rational
mp forall a. Eq a => a -> a -> Bool
== forall k a. Map k a
M.empty  = forall a. a -> Maybe a
Just Rational
0
    | Bool
otherwise      = forall k a. Ord k => k -> Map k a -> Maybe a
M.lookup Integer
0 Map Integer Rational
mp
toRat Cyclotomic
_ = forall a. Maybe a
Nothing

-- | Sine function with argument in degrees.
sinDeg :: Rational -> Cyclotomic
sinDeg :: Rational -> Cyclotomic
sinDeg Rational
d = let n :: Rational
n = Rational
d forall a. Fractional a => a -> a -> a
/ Rational
360
               nm :: Integer
nm = forall a. Num a => a -> a
abs (forall a. Ratio a -> a
numerator Rational
n)
               dn :: Integer
dn = forall a. Ratio a -> a
denominator Rational
n
               a :: Cyclotomic
a = Integer -> Cyclotomic
e Integer
dnforall a b. (Num a, Integral b) => a -> b -> a
^Integer
nm
           in forall a. Fractional a => Rational -> a
fromRational(forall a. Num a => a -> a
signum Rational
d) forall a. Num a => a -> a -> a
* (Cyclotomic
a forall a. Num a => a -> a -> a
- Cyclotomic -> Cyclotomic
conj Cyclotomic
a) forall a. Fractional a => a -> a -> a
/ (Cyclotomic
2forall a. Num a => a -> a -> a
*Cyclotomic
i)

-- | Cosine function with argument in degrees.
cosDeg :: Rational -> Cyclotomic
cosDeg :: Rational -> Cyclotomic
cosDeg Rational
d = let n :: Rational
n = Rational
d forall a. Fractional a => a -> a -> a
/ Rational
360
               nm :: Integer
nm = forall a. Num a => a -> a
abs (forall a. Ratio a -> a
numerator Rational
n)
               dn :: Integer
dn = forall a. Ratio a -> a
denominator Rational
n
               a :: Cyclotomic
a = Integer -> Cyclotomic
e Integer
dnforall a b. (Num a, Integral b) => a -> b -> a
^Integer
nm
           in (Cyclotomic
a forall a. Num a => a -> a -> a
+ Cyclotomic -> Cyclotomic
conj Cyclotomic
a) forall a. Fractional a => a -> a -> a
/ Cyclotomic
2

-- | Sine function with argument in revolutions.
sinRev :: Rational -> Cyclotomic
sinRev :: Rational -> Cyclotomic
sinRev Rational
n = let nm :: Integer
nm = forall a. Num a => a -> a
abs (forall a. Ratio a -> a
numerator Rational
n)
               dn :: Integer
dn = forall a. Ratio a -> a
denominator Rational
n
               a :: Cyclotomic
a = Integer -> Cyclotomic
e Integer
dnforall a b. (Num a, Integral b) => a -> b -> a
^Integer
nm
           in forall a. Fractional a => Rational -> a
fromRational(forall a. Num a => a -> a
signum Rational
n) forall a. Num a => a -> a -> a
* (Cyclotomic
a forall a. Num a => a -> a -> a
- Cyclotomic -> Cyclotomic
conj Cyclotomic
a) forall a. Fractional a => a -> a -> a
/ (Cyclotomic
2forall a. Num a => a -> a -> a
*Cyclotomic
i)

-- | Cosine function with argument in revolutions.
cosRev :: Rational -> Cyclotomic
cosRev :: Rational -> Cyclotomic
cosRev Rational
n = let nm :: Integer
nm = forall a. Num a => a -> a
abs (forall a. Ratio a -> a
numerator Rational
n)
               dn :: Integer
dn = forall a. Ratio a -> a
denominator Rational
n
               a :: Cyclotomic
a = Integer -> Cyclotomic
e Integer
dnforall a b. (Num a, Integral b) => a -> b -> a
^Integer
nm
           in (Cyclotomic
a forall a. Num a => a -> a -> a
+ Cyclotomic -> Cyclotomic
conj Cyclotomic
a) forall a. Fractional a => a -> a -> a
/ Cyclotomic
2

gcdList :: [Integer] -> Integer
gcdList :: [Integer] -> Integer
gcdList [] = forall a. HasCallStack => [Char] -> a
error [Char]
"gcdList called on empty list"
gcdList (Integer
n:[Integer]
ns) = forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr forall a. Integral a => a -> a -> a
gcd Integer
n [Integer]
ns

equal :: Eq a => [a] -> Bool
equal :: forall a. Eq a => [a] -> Bool
equal [] = Bool
True
equal [a
_] = Bool
True
equal (a
x:a
y:[a]
ys) = a
x forall a. Eq a => a -> a -> Bool
== a
y Bool -> Bool -> Bool
&& forall a. Eq a => [a] -> Bool
equal (a
yforall a. a -> [a] -> [a]
:[a]
ys)

-- | The golden ratio, @(1 + √5)/2@.
goldenRatio :: Cyclotomic
goldenRatio :: Cyclotomic
goldenRatio = (Cyclotomic
1 forall a. Num a => a -> a -> a
+ Rational -> Cyclotomic
sqrtRat Rational
5) forall a. Fractional a => a -> a -> a
/ Cyclotomic
2

-- | Discrete Fourier transform,
--   @X_k = \sum_{n=0}^{N-1} x_n \cdot e^{-i 2 \pi \frac{k}{N} n}@.
dft :: [Cyclotomic] -> [Cyclotomic]
dft :: [Cyclotomic] -> [Cyclotomic]
dft [Cyclotomic]
cs = [forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
sum forall a b. (a -> b) -> a -> b
$ forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith forall a. Num a => a -> a -> a
(*) [Cyclotomic -> Cyclotomic
conj (Integer -> Cyclotomic
e Integer
mforall a b. (Num a, Integral b) => a -> b -> a
^(Integer
kforall a. Num a => a -> a -> a
*Integer
n)) | Integer
n <- [Integer
0..]] [Cyclotomic]
cs | Integer
k <- [Integer
0..Integer
mforall a. Num a => a -> a -> a
-Integer
1]]
          where m :: Integer
m = forall a b. (Integral a, Num b) => a -> b
fromIntegral forall a b. (a -> b) -> a -> b
$ forall (t :: * -> *) a. Foldable t => t a -> Int
length [Cyclotomic]
cs

-- | Inverse discrete Fourier transform,
--   @x_n = \frac{1}{N} \sum_{k=0}^{N-1} X_k \cdot e^{i 2 \pi \frac{k}{N} n}@.
dftInv :: [Cyclotomic] -> [Cyclotomic]
dftInv :: [Cyclotomic] -> [Cyclotomic]
dftInv [Cyclotomic]
cs = [Cyclotomic
minv forall a. Num a => a -> a -> a
* forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
sum (forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith forall a. Num a => a -> a -> a
(*) [Integer -> Cyclotomic
e Integer
mforall a b. (Num a, Integral b) => a -> b -> a
^(Integer
kforall a. Num a => a -> a -> a
*Integer
n) | Integer
n <- [Integer
0..]] [Cyclotomic]
cs) | Integer
k <- [Integer
0..Integer
mforall a. Num a => a -> a -> a
-Integer
1]]
          where m :: Integer
m = forall a b. (Integral a, Num b) => a -> b
fromIntegral forall a b. (a -> b) -> a -> b
$ forall (t :: * -> *) a. Foldable t => t a -> Int
length [Cyclotomic]
cs
                minv :: Cyclotomic
minv = forall a. Fractional a => Rational -> a
fromRational (Integer
1 forall a. Integral a => a -> a -> Ratio a
% Integer
m)

-- | Solutions to the quadratic equation
--   a x^2 + b x + c = 0.
--   Returns 'Nothing' if a == 0.
rootsQuadEq :: Rational  -- ^ a
            -> Rational  -- ^ b
            -> Rational  -- ^ c
            -> Maybe (Cyclotomic,Cyclotomic)  -- ^ roots
rootsQuadEq :: Rational -> Rational -> Rational -> Maybe (Cyclotomic, Cyclotomic)
rootsQuadEq Rational
a Rational
b Rational
c
    | Rational
a forall a. Eq a => a -> a -> Bool
== Rational
0     = forall a. Maybe a
Nothing
    | Bool
otherwise  = forall a. a -> Maybe a
Just ((-Cyclotomic
bb forall a. Num a => a -> a -> a
+ Cyclotomic
sqrtDisc)forall a. Fractional a => a -> a -> a
/(Cyclotomic
2forall a. Num a => a -> a -> a
*Cyclotomic
aa),(-Cyclotomic
bb forall a. Num a => a -> a -> a
- Cyclotomic
sqrtDisc)forall a. Fractional a => a -> a -> a
/(Cyclotomic
2forall a. Num a => a -> a -> a
*Cyclotomic
aa))
    where
      aa :: Cyclotomic
aa = forall a. Fractional a => Rational -> a
fromRational Rational
a
      bb :: Cyclotomic
bb = forall a. Fractional a => Rational -> a
fromRational Rational
b
      sqrtDisc :: Cyclotomic
sqrtDisc = Rational -> Cyclotomic
sqrtRat (Rational
bforall a. Num a => a -> a -> a
*Rational
b forall a. Num a => a -> a -> a
- Rational
4forall a. Num a => a -> a -> a
*Rational
aforall a. Num a => a -> a -> a
*Rational
c)

-- | Heron's formula for the area of a triangle with
--   side lengths a, b, c.
heron :: Rational    -- ^ a
      -> Rational    -- ^ b
      -> Rational    -- ^ c
      -> Cyclotomic  -- ^ area of triangle
heron :: Rational -> Rational -> Rational -> Cyclotomic
heron Rational
a Rational
b Rational
c
    = Rational -> Cyclotomic
sqrtRat (Rational
s forall a. Num a => a -> a -> a
* (Rational
sforall a. Num a => a -> a -> a
-Rational
a) forall a. Num a => a -> a -> a
* (Rational
sforall a. Num a => a -> a -> a
-Rational
b) forall a. Num a => a -> a -> a
* (Rational
sforall a. Num a => a -> a -> a
-Rational
c))
      where
        s :: Rational
s = (Rational
a forall a. Num a => a -> a -> a
+ Rational
b forall a. Num a => a -> a -> a
+ Rational
c) forall a. Fractional a => a -> a -> a
/ Rational
2