cyclotomic 0.1 → 0.2

raw patch · 2 files changed

+106/−49 lines, 2 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• cyclotomic.cabal +1/−1
• src/Data/Complex/Cyclotomic.hs +105/−48

@@ -1,5 +1,5 @@ Name:                cyclotomic-Version:             0.1+Version:             0.2 Synopsis:            A subfield of the complex numbers for exact calculation Description:         The cyclotomic numbers are a subset of the                      complex numbers with a number of nice properties.

@@ -1,32 +1,61 @@ {-# OPTIONS_GHC -Wall #-} --- | 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'.------   This algorithm for cyclotomic numbers is adapted from code by---   Martin Schoenert and Thomas Breuer in the GAP project <http://www.gap-system.org/> .---   See in particular source files gap4r4\/src\/cyclotom.c and---   gap4r4\/lib\/cyclotom.gi .+-- Module      :  Data.Complex.Cyclotomic+-- Copyright   :  (c) Scott N. Walck 2012+-- License     :  GPL-3 (see LICENSE)+-- Maintainer  :  Scott N. Walck <walck@lvc.edu> +{- | 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@@ -35,14 +64,17 @@     ,sqrtRat     ,sinDeg     ,cosDeg+    ,gaussianRat+    ,polarRat     ,conj     ,real     ,imag     ,modSq-    ,toComplex     ,isReal-    ,isRational-    ,isGaussianRational+    ,isRat+    ,isGaussianRat+    ,toComplex+    ,toReal     ,toRat     )     where@@ -58,22 +90,26 @@                              , coeffs :: M.Map Integer Rational                              } deriving (Eq) +-- | @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     (+) = sumCyc     (*) = prodCyc     (-) c1 c2 = sumCyc c1 (aInvCyc c2)     negate = aInvCyc     abs = sqrtRat . modSq-    signum = error "signum not defined for cyclotomic numbers"+    signum 0 = zeroCyc+    signum c = c / abs c     fromInteger 0 = zeroCyc     fromInteger n = Cyclotomic 1 (M.singleton 0 (fromIntegral n))  instance Fractional Cyclotomic where     recip = invCyc+    fromRational 0 = zeroCyc     fromRational r = Cyclotomic 1 (M.singleton 0 r) --- | The primitive 'n'th root of unity.---   For example, 'e'(4) = 'i' is the primitive 4th root of unity,+-- | 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@@ -164,6 +200,19 @@ i :: Cyclotomic i = e 4 +-- | Make a Gaussian rational; @gaussianRat p q@ is the same as @p + q * i@.+gaussianRat :: Rational -> Rational -> Cyclotomic+gaussianRat p q = fromRational p + fromRational q * 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@.+polarRat :: Rational -> Rational -> Cyclotomic+polarRat r s = fromRational r * e q ^ p+    where+      p = numerator s+      q = denominator s+ -- | Complex conjugate. conj :: Cyclotomic -> Cyclotomic conj (Cyclotomic n mp)@@ -183,12 +232,6 @@             Just msq -> msq             Nothing  -> error $ "modSq:  tried z = " ++ show z --- | Export as an inexact complex number.-toComplex :: Cyclotomic -> Complex Double-toComplex c = sum [fromRational r * en^p | (p,r) <- M.toList (coeffs c)]-    where en = exp (0 :+ 2*pi/n)-          n = fromIntegral (order c)- convertToBase :: Integer -> M.Map Integer Rational -> M.Map Integer Rational convertToBase n mp = foldr (\(p,r) m -> replace n p r m) mp (extraneousPowers n) @@ -304,10 +347,12 @@  -- | Product of two cyclotomic numbers. prodCyc :: Cyclotomic -> Cyclotomic -> Cyclotomic-prodCyc (Cyclotomic o1 m1) (Cyclotomic o2 m2)-    = mkCyclotomic ord $ M.fromListWith (+)-      [((o2*e1+o1*e2) `mod` ord,c1*c2) | (e1,c1) <- M.toList m1, (e2,c2) <- M.toList m2]-      where ord = o1 * o2+prodCyc (Cyclotomic o1 map1) (Cyclotomic o2 map2)+    = let ord = lcm o1 o2+          m1 = ord `div` o1+          m2 = ord `div` o2+      in mkCyclotomic ord $ M.fromListWith (+)+             [((m1*e1+m2*e2) `mod` ord,c1*c2) | (e1,c1) <- M.toList map1, (e2,c2) <- M.toList map2]  -- | Product of a rational number and a cyclotomic number. prodRatCyc :: Rational -> Cyclotomic -> Cyclotomic@@ -331,15 +376,27 @@ isReal c = c == conj c  -- | Is the cyclotomic a rational?-isRational :: Cyclotomic -> Bool-isRational (Cyclotomic 1 _) = True-isRational _                = False+isRat :: Cyclotomic -> Bool+isRat (Cyclotomic 1 _) = True+isRat _                = False  -- | Is the cyclotomic a Gaussian rational?-isGaussianRational :: Cyclotomic -> Bool-isGaussianRational c = isRational (real c) && isRational (imag c)+isGaussianRat :: Cyclotomic -> Bool+isGaussianRat c = isRat (real c) && isRat (imag c) --- | Return Just rational if the cyclotomic is rational, Nothing otherwise.+-- | Export as an inexact complex number.+toComplex :: Cyclotomic -> Complex Double+toComplex c = sum [fromRational r * en^p | (p,r) <- M.toList (coeffs c)]+    where en = exp (0 :+ 2*pi/n)+          n = fromIntegral (order c)++-- | Export as an inexact real number if possible.+toReal :: Cyclotomic -> Maybe Double+toReal c+    | isReal c   = Just $ realPart (toComplex c)+    | otherwise  = Nothing++-- | Return an exact rational number if possible. toRat :: Cyclotomic -> Maybe Rational toRat (Cyclotomic 1 mp)     | mp == M.empty  = Just 0