canon 0.1.0.0 → 0.1.0.1

raw patch · 7 files changed

+55/−58 lines, 7 filesPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

API changes (from Hackage documentation)

Files

• Changes +5/−0
• Math/NumberTheory/Canon.hs +11/−12
• Math/NumberTheory/Canon/Additive.hs +4/−4
• Math/NumberTheory/Canon/AurifCyclo.hs +18/−25
• Math/NumberTheory/Canon/Internals.hs +12/−12
• Math/NumberTheory/Canon/Simple.hs +3/−3
• canon.cabal +2/−2

@@ -1,2 +1,7 @@+0.1.0.1:+    Improvements to documentation.+    Fix typos and word omissions.+    Remove unused / "unsafe" Cr functions from AurifCyclo.hs+ 0.1.0.0:     First release

@@ -49,12 +49,12 @@ data Canon = Bare Integer BareStatus | Canonical GCR_ CanonValueType   -- | BareStatus: A "Bare Simplified" number means a prime number, +/-1 or 0.  The code must set the flag properly---               A "Bare NotSimplified" number is an integer that has not been checked (to see if it can be factored).+--               A "Bare NotSimplified" number is an Integer that has not been checked (to see if it can be factored). data BareStatus = Simplified | NotSimplified deriving (Eq, Ord, Show)  makeCanon, makeC, makeCanonFull, makeDefCanonForExpnt :: Integer -> Canon --- | Create a Canon from an integer.  This may involve expensive factorization.+-- | Create a Canon from an Integer.  This may involve expensive factorization. makeCanon n = makeCanonI n False  -- | Shorthand for makeCanon@@ -141,7 +141,7 @@   abs x         = cAbs    x   signum x      = cSignum x --- | Is the Canon a more complex expression? +-- | Checks if the Canon is Canonical, a more complex expression. cCanonical :: Canon -> Bool cCanonical (Canonical _ _ ) = True cCanonical _                = False@@ -179,7 +179,7 @@  cEq (Canonical x a )       (Canonical y b)        = if a /= b then False else gcrEqCheck x y --- | Check if a Canon is an odd integer.  Note: If the Canon is not integral, return False +-- | Check if a Canon is an odd Integer.  Note: If the Canon is not integral, return False  cOdd :: Canon -> Bool cOdd (Bare x _)               = mod x 2 == 1 cOdd (Canonical c IntegralC ) = gcrOdd c@@ -260,8 +260,7 @@  cPhi = cTotient --- | Hyperoperations (including tetration and beyond): https://en.wikipedia.org/wiki/Hyperoperation--- | The thinking around the operators is that they should look progressively scarier :)+-- | The thinking around the hyperoperators is that they should look progressively scarier :) infixr 9 <^>, <<^>>, <<<^>>> (<^>), (<<^>>), (<<<^>>>) :: Canon -> Integer -> Canon a <^>     b = fst $ cTetration a b crCycloInitMap@@ -279,7 +278,7 @@ -- | Hexation Function cHexation  = cHyperOp 6 --- | Generalized Hyperoperation Function+-- | Generalized Hyperoperation Function (https://en.wikipedia.org/wiki/Hyperoperation) cHyperOp :: Integer -> Canon -> Integer -> CycloMap -> (Canon, CycloMap) cHyperOp n a b m | b < -1                       = error "Hyperoperations not defined when b < -1"                  | n < 0                        = error "Hyperoperations require the level n >= 0"@@ -415,14 +414,14 @@ cToI :: Canon -> Integer cToI (Bare i _ )     = i cToI (Canonical c v) | v == IntegralC = gcrToI c -                     | otherwise      = error "Can't convert non-integral canon to an integer"+                     | otherwise      = error "Can't convert non-integral Canon to an Integer"  -- | Convert Canon To Double. cToD :: Canon -> Double cToD (Bare i _ )      = fromIntegral i cToD (Canonical c _ ) = gcrToD c  --- | Multiply Function: Generally speaking this will be much cheaper.+-- | Multiply Function: Generally speaking, this will be much cheaper. cMult :: Canon -> Canon -> CycloMap -> (Canon, CycloMap)  cMult Pc0 _   m = (c0, m) cMult _   Pc0 m = (c0, m)@@ -522,7 +521,7 @@ cReciprocal :: Canon -> Canon cReciprocal x = fst $ cExp x cN1 True crCycloInitMap  -- raise number to (-1)st power --- | Functions to check if a Canon is integral, (ir)rational, "simplified" or a prime tower+-- | Functions to check if a Canon is Integral, (Ir)Rational, "Simplified" or a prime tower cIntegral, cIrrational, cRational, cSimplified, cIsPrimeTower :: Canon -> Bool  cIntegral (Bare      _ _ ) = True@@ -581,7 +580,7 @@                                               | otherwise                = cPrimeTowerLevelI (snd $ head g) n (l+1) cPrimeTowerLevelI _                       _ _ = 0 --- | Functions to Convert Canon to Generalized Canon Rep+-- | Functions to convert Canon to generalized canon rep canonToGCR, cToGCR :: Canon -> GCR_ canonToGCR (Canonical x _) = x canonToGCR (Bare x NotSimplified) = canonToGCR $ makeCanon x -- ToDo: Thread in CycloMap?@@ -676,7 +675,7 @@ gcrLog :: GCR_ -> Rational gcrLog g = crLog $ gcrToCR g    --- | These internal functions should not be called directly.  The definition of GCD and LCM are extended to handle non-integers.+-- | These internal functions should not be called directly.  The definition of GCD and LCM are extended to handle non-Integers. gcrGCD, gcrLCM :: GCR_ -> GCR_ -> GCR_ gcrGCD POne _    = gcr1 gcrGCD _    POne = gcr1

@@ -22,7 +22,7 @@ import Math.NumberTheory.Canon.Internals import Math.NumberTheory.Canon.AurifCyclo (crCycloAurifApply, CycloMap) --- | Functions for computing sums and differences.  +-- | Functions for computing sums and differences crAdd, crSubtract, crAddR, crSubtractR :: CR_ -> CR_ -> CycloMap -> (CR_, CycloMap) crAdd       = crApplyAdtvOpt  True  crSubtract  = crApplyAdtvOpt  False@@ -59,7 +59,7 @@                                             n        = crMult ngcd nf                                             d        = crMult dx dy   --- | crApplyAdtvOpt: Simplifies/Factorizes expressions x +/- y.+-- | Simplify / Factorize expressions of the form: x +/- y. crApplyAdtvOpt :: Bool -> CR_ -> CR_ -> CycloMap -> (CR_, CycloMap) crApplyAdtvOpt _     x     PZero m = (x, m) crApplyAdtvOpt True  PZero y     m = (y, m)           -- True -> (+)@@ -73,7 +73,7 @@ logThreshold :: Double logThreshold = 10 * (log 10) -- 'n' digit number --- | crApplyAdtvOptConv is setup to convert different cases in a standard manner.  All 8 combinations of signs and operators are covered here.+-- | Convert different sign / operator cases in a standard manner.  All 8 combinations are covered here. {-   p1 + p2 => p1 + p2,     p1 - p2 => p1 - p2   p1 + n2 => p1 - p2,     p1 - n2 => p1 + p2@@ -99,7 +99,7 @@           (c1, m1) = crCycloAurifApply b       ax ay g gi m           (c2, m2) = crCycloAurifApply (not b) ax ay g gi m -- corresponds to "otherwise" --- | Quot Rem function for Canon Rep.  Optimization: Check first if q is a multiple of r.  If so, we avoid the potentially expensive conversion.+-- | Quot Rem function for CR_.  Optimization: Check first if q is a multiple of r.  If so, we avoid the potentially expensive conversion. crQuotRem :: CR_ -> CR_ -> CycloMap -> ((CR_, CR_), CycloMap) crQuotRem x y m = case (crDiv x y) of                     Left  _        -> ((q,        md), m') 

@@ -10,12 +10,12 @@ {-# LANGUAGE PatternSynonyms, ViewPatterns #-}  module Math.NumberTheory.Canon.AurifCyclo (-  aurCandDec,     aurCandDecCr, -  aurDec,         aurDecCr,+  aurCandDec,     +  aurDec,            applyCycloPair, applyCycloPairWithMap,   cyclo,          cycloWithMap,   cycloDivSet,    cycloDivSetWithMap,-  chineseAurif,   chineseAurifWithMap, chineseAurifCr,+  chineseAurif,   chineseAurifWithMap,     crCycloAurifApply, applyCrCycloPair, divvy,   CycloMap, fromCycloMap, fromCM, showCyclo, crCycloInitMap@@ -64,7 +64,7 @@         cycA x' y' n  = (sort ia, m') -- sort the integers returned from low to high, should help if there are larger terms                         where (ia, m') = applyCrCycloPair x' y' n m         eA (a,mp)     = (foldr1 crMult $ map crFromI v, m') -- eA stands for "enriched apply"-                        where (v, m')   = case aurCandDecU x y gi g b of+                        where (v, m')   = case aurCandDecI x y gi g b of                                             Nothing       -> auL a mp  -- can't do anything Brent Aurif-wise, try Chinese method                                             Just (a1, a2) -> auL (divvy a a1 a2) mp -- meld in the 2 Aurif factors with input array                               auL al ma = case c of -- aL stands for "augmented list)@@ -84,22 +84,19 @@ http://maths-people.anu.edu.au/~brent/pd/rpb135.pdf -} --- | Integer wrapper for aurCandDecCr-aurCandDec :: Integer -> Integer -> Bool -> Maybe (Integer, Integer)-aurCandDec xi yi b = aurCandDecCr (crFromI xi) (crFromI yi) b- -- | This function checks if the input is a candidate for Aurifeuillian decomposition.---   If so, split it into two and evaluate it.  Otherwise, return nothing.  ---   The code will "prep" the input params so they will be relatively prime.-aurCandDecCr :: CR_ -> CR_ -> Bool -> Maybe (Integer, Integer)-aurCandDecCr xp yp b = aurCandDecU x y n (crFromI n) b -                       where n      = gcd (crMaxRoot $ crAbs x) (crMaxRoot $ crAbs y)-                             gxy    = crGCD xp yp -                             (x, y) = (crDivStrict xp gxy, crDivStrict yp gxy) -- this will fix the input to be relatively prime+--   If so, split it into two and evaluate it.  Otherwise, return nothing.+--   The code will "prep" the input params for the internal function so they will be relatively prime.+aurCandDec :: Integer -> Integer -> Bool -> Maybe (Integer, Integer)+aurCandDec xi yi b = f (crFromI xi) (crFromI yi)+                     where f xp yp = aurCandDecI x y n (crFromI n) b +                                     where n      = gcd (crMaxRoot $ crAbs x) (crMaxRoot $ crAbs y)+                                           gxy    = crGCD xp yp +                                           (x, y) = (crDivStrict xp gxy, crDivStrict yp gxy) -- this will fix the input to be relatively prime --- U belows means unsafe.  Don't call this directly.  The function assumes that x and y are relatively prime.  Currently uses Brent logic only-aurCandDecU :: CR_ -> CR_ -> Integer -> CR_ -> Bool -> Maybe (Integer, Integer)-aurCandDecU x y n cr b| (nm4 == 1 && b) || (nm4 /= 1 && not b) ||+-- Don't call this I(nternal) function directly.  The function assumes that x and y are relatively prime.  Currently uses Brent logic only.+aurCandDecI :: CR_ -> CR_ -> Integer -> CR_ -> Bool -> Maybe (Integer, Integer)+aurCandDecI x y n cr b| (nm4 == 1 && b) || (nm4 /= 1 && not b) ||                         (xdg == x && ydg == y)  || (m /= 0)                                         = Nothing --                        | otherwise       = case aurDecI n' cr' of@@ -110,7 +107,7 @@                             -- this will only work when either x or y = 1 and not for any other divisor of g.                               -- If both terms are not 1, we just attempt an Aurif. decomp for n   -                            -- need to integrate chineseAurif, it does something different                          +                            -- TODO: Need to integrate chineseAurif as it does something different                                                       (n', cr') | x /= cr1 && y /= cr1 = (n, cr)                                        | otherwise            = (gcd1i, gcd1)                                       where x1    = if y /= cr1 then y else x@@ -154,10 +151,6 @@ aurDec n | n <= 1    = error "aurifDecomp: n must be greater than 1"          | otherwise = aurDecI n (crFromI n) --- | CR_ wrapper for aurDec -aurDecCr :: CR_ -> Maybe (Array Integer Integer, Array Integer Integer)                -aurDecCr cr = aurDec (crToI cr)- -- | Internal Aurifeullian Decomposition Workhorse Function aurDecI :: Integer -> CR_ -> Maybe (Array Integer Integer, Array Integer Integer)  aurDecI n cr | crHasSquare cr || n < 2 || n' < 2@@ -249,7 +242,7 @@     C(15) is a form of the last term where y = 1     It's possible in some cases to do an additional Aurifeullian factorization (of the last term).   -} --- | CycloPair: Pair of an Integer and its Corresponding Cyclotomic Polynomial+-- | CycloPair: Pair of an Integer and its corresponding cyclotomic polynomial type CycloPair         = (Integer, Poly Float)  -- | CycloMapInternal: Map internal to CycloMap newtype@@ -360,7 +353,7 @@                                           f _        p' mp = (p', mp)                         mf []     = error "Logic error: Blank list can't be passed to mf aka crCycloMemoFold"  --- Return a pair of Integer and its Cyclotomic Polynomial while efficiently building up a cyc. poly. map+-- | Return a pair of Integer and its cyclotomic polynomial while efficiently building up a map crCycloAll :: CR_ -> CycloMap -> (CycloPair, CycloMap) crCycloAll cr m | p == cr1     = case cmLookup cr m of                                     Nothing -> error "Logic error: Radical value not found for crCycloAll"

@@ -77,9 +77,9 @@   pattern PIntNPos,   pattern PIntPos, -  -- functions deprecated from arithmoi that needed to be included here+  -- Functions deprecated from arithmoi that needed to be included here   totient,-  pmI -- stands for powerModInteger+  pmI -- Short for powerModInteger )  where @@ -100,7 +100,7 @@    One               []         Other Positive -   Numbers:          A set of (p,e) pairs where the p's are prime and in ascending order. +   Numbers:          A set of (p,e) pairs where the p(rime)s are in ascending order.                       For "integers",  the e(xponents) must be positive                      For "rationals", the e(xponents) must not be zero                      All "integers" are "rationals" but not vice-versa.@@ -246,7 +246,7 @@  crToInteger, crToI :: CR_ -> Integer --- | Converts a canon rep back to an Integer.+-- | Convert a canon rep back to an Integer. crToInteger POne                  = 1 crToInteger PZero                 = 0 crToInteger c | (head c) == creN1 = -1 * (crToInteger $ tail c)    -- negative number@@ -290,7 +290,7 @@ crShow x    | null (tail x) = ceShow $ head x             | otherwise     = concat $ intersperse " * " $ map ceShow x  --- | Display a Canonical Rep rationally, as a quotient of its numerator and denominator.+-- | Display a CR_ rationally, as a quotient of its numerator and denominator. crShowRational c | d == cr1  = crShow n                  | otherwise = crShow n ++ "\n/\n" ++ crShow d                  where (n, d) = crSplit c  @@ -302,7 +302,7 @@ crNegate x | crNegative x = tail x             | otherwise    = creN1 : x  --- | Take the Absolute Value of a CR_.+-- | Take the absolute value of a CR_. crAbs x | crNegative x = tail x         | otherwise    = x @@ -353,7 +353,7 @@ zeroDivZeroError = "Zero divided by zero is undefined!" negativeLogError = "The log of a negative number is undefined!" --- | Strict division: Generates error if exact division is not possible.+-- | Strict division: Generate error if exact division is not possible. crDivStrict :: CR_ -> CR_ -> CR_ crDivStrict x y = case crDiv x y of                     Left errorMsg  -> error errorMsg@@ -518,10 +518,10 @@ crPrime PPrime = True crPrime _      = False --- | Checks if a number has a squared (or higher) factor.+-- | Check if a number has a squared (or higher) factor. crHasSquare    = any (\(_,e) -> e > 1)                      --- | Divisor functions -- should be called with integral CRs (no negative exponents).+-- | Divisor functions should be called with integral CRs (no negative exponents). crNumDivisors, crTau, crTotient, crPhi  :: CR_ -> Integer  crNumDivisors cr = product $ map (\(_,e) -> 1 + e) cr -- does return 1 for cr1@@ -529,7 +529,7 @@ crTotient     cr = product $ map (\(p,e) -> (p-1) * p^(e-1)) cr crPhi            = crTotient --- | Computes the nth divisor. This is zero based. +-- | Compute the nth divisor. This is zero based.  --   Note: This is deterministic but it's not ordered by the value of the divisor. crNthDivisor :: Integer -> CR_ -> CR_ crNthDivisor 0 _    = cr1@@ -540,7 +540,7 @@                           r          = crNthDivisor (div n (ce + 1)) cs -- first param is the next n                           m          = mod n (ce + 1)           --- | Consider this to be an inverse of the crNthDivisor function.+-- | Consider this to be the inverse of the crNthDivisor function. crWhichDivisor :: CR_ -> CR_ -> Integer crWhichDivisor d c | crPositive d == False ||                      crPositive c == False = error "crWhichDivisor: Both params must be positive"@@ -554,7 +554,7 @@                                                                                        where ((dp, de):ds)  = d'                                                                                              ((cp, ce):cs)  = c'    --- | Efficiently computes all of the divisors based on the canonical representation.+-- | Efficiently compute all of the divisors based on the canonical representation. crDivisors :: CR_ -> [CR_] crDivisors c = foldr1 cartProd $ map pwrDivList c                where cartProd xs ys   = [x ++ y | y <- ys, x <- xs]

@@ -78,14 +78,14 @@              instance Fractional SimpleCanon where   fromRational (n :% d) | m == 0    = MakeSC $ crFromI q-                        | otherwise = error "Modulus not zero.  Use Rational SimpleCanons for non-integers."+                        | otherwise = error "Modulus not zero.  Use Rational SimpleCanons for non-Integers."                         where (q, m) = quotRem n d   (/) x y               = MakeSC $ crDivStrict (fromSC x) (fromSC y)  instance Num SimpleCanon where   fromInteger n = MakeSC $ crFromI n    -- to do: check where called?-  x + y         = MakeSC $ fst $ crAdd      (fromSC x) (fromSC y) crCycloInitMap -- discard the map info-  x - y         = MakeSC $ fst $ crSubtract (fromSC x) (fromSC y) crCycloInitMap -- discard the map info+  x + y         = MakeSC $ fst $ crAdd      (fromSC x) (fromSC y) crCycloInitMap -- discard the map+  x - y         = MakeSC $ fst $ crSubtract (fromSC x) (fromSC y) crCycloInitMap -- discard the map   x * y         = MakeSC $ crMult     (fromSC x) (fromSC y)      negate x      = MakeSC $ crNegate $ fromSC x

@@ -2,9 +2,9 @@ --  see http://haskell.org/cabal/users-guide/  name:                canon-version:             0.1.0.0+version:             0.1.0.1 synopsis:            Massive Number Arithmetic-description:         This library allows one to manipulate of practically unlimited by keeping them in factored "canonical" form.+description:         This library allows one to manipulate numbers of practically unlimited size by keeping them in factored "canonical" form.                      For manipulating sums and differences, there is additional code to factor expressions of special forms.  homepage:            https://github.com/grandpascorpion/canon