pell 0.1.0.0 → 0.1.1.0
raw patch · 10 files changed
+122/−133 lines, 10 filesdep ~basePVP ok
version bump matches the API change (PVP)
Dependency ranges changed: base
API changes (from Hackage documentation)
Files
- Math/NumberTheory/Moduli/SquareRoots.hs +7/−6
- Math/NumberTheory/Moduli/SquareRoots/Test.hs +8/−7
- Math/NumberTheory/Pell.hs +23/−22
- Math/NumberTheory/Pell/PQa.hs +19/−17
- Math/NumberTheory/Pell/Test.hs +16/−30
- Math/NumberTheory/Pell/Test/Reduced.hs +11/−9
- Math/NumberTheory/Pell/Test/Solve.hs +12/−11
- Math/NumberTheory/Pell/Test/Utils.hs +3/−2
- dist/build/test-pellStub/test-pellStub-tmp/test-pellStub.hs +0/−5
- pell.cabal +23/−24
Math/NumberTheory/Moduli/SquareRoots.hs view
@@ -1,18 +1,19 @@ -- | -- Module: Math.NumberTheory.Moduli.SquareRoots--- Copyright: (c) 2015 by Dr. Lars Brünjes+-- Copyright: (c) 2016 by Dr. Lars Brünjes -- Licence: MIT--- Maintainer: Dr. Lars Brünjes <lbrunjes@gmx.de>+-- Maintainer: Dr. Lars Brünjes <brunjlar@gmail.com> -- Stability: Provisional -- Portability: portable -- -- This module provides a function to find all square roots of a number modulo another number.-module Math.NumberTheory.Moduli.SquareRoots (- sqrts ) where+module Math.NumberTheory.Moduli.SquareRoots+ ( sqrts+ ) where -import Data.List (sort)+import Data.List (sort) import Math.NumberTheory.Primes.Factorisation (factorise)-import Math.NumberTheory.Moduli (chineseRemainder, sqrtModPPList)+import Math.NumberTheory.Moduli (chineseRemainder, sqrtModPPList) chineseRemainders :: [([Integer], Integer)] -> [Integer] chineseRemainders = fst . go where
Math/NumberTheory/Moduli/SquareRoots/Test.hs view
@@ -1,8 +1,9 @@-module Math.NumberTheory.Moduli.SquareRoots.Test (- prop_sqrtsPP,- prop_sqrts) where+module Math.NumberTheory.Moduli.SquareRoots.Test+ ( prop_sqrtsPP+ , prop_sqrts+ ) where -import Data.Numbers.Primes (primes)+import Data.Numbers.Primes (primes) import Math.NumberTheory.Moduli.SquareRoots (sqrts) import Test.QuickCheck @@ -19,7 +20,7 @@ e <- choose (1, 20) return $ PrimePower (primes !! indexP, e) - shrink (PrimePower (p, e)) = + shrink (PrimePower (p, e)) = map PrimePower $ [(p', e) | p' <- takeWhile (< p) primes] ++ [(p, e') | e' <- [1, e - 1]] newtype ProblemPP = ProblemPP (Integer, PrimePower) deriving (Show, Eq)@@ -30,14 +31,14 @@ pp <- arbitrary a <- choose (0, evalPP pp - 1) return $ ProblemPP (a, pp)- + shrink (ProblemPP (a, pp)) = map ProblemPP $ [(a', pp) | a' <- [0, a - 1]] ++ [(a, pp') | pp' <- shrink pp, evalPP pp' > a] newtype Problem = Problem (Integer, Integer) deriving (Show, Eq) instance Arbitrary Problem where- + arbitrary = do m <- suchThat arbitrary (> 0) a <- choose (0, m - 1)
Math/NumberTheory/Pell.hs view
@@ -1,31 +1,32 @@ -- | -- Module: Math.NumberTheory.Pell--- Copyright: (c) 2015 by Dr. Lars Brünjes+-- Copyright: (c) 2016 by Dr. Lars Brünjes -- Licence: MIT--- Maintainer: Dr. Lars Brünjes <lbrunjes@gmx.de>+-- Maintainer: Dr. Lars Brünjes <brunjlar@gmail.com> -- Stability: Provisional -- Portability: portable ----- This module provides a function to solve generalized Pell Equations, +-- This module provides a function to solve generalized Pell Equations, -- using the "LMM Algorithm" described by John P. Robertson in--- <http://http://www.jpr2718.org/pell.pdf>.+-- <http://www.jpr2718.org/pell.pdf>. -- A /generalized Pell Equation/ is a diophantine equation of the form -- @x^2 - dy^2 = n@, where @d@ is a positive integer which is not a square -- and where @n@ is a non-zero integer. -- We are looking for solutions @(x,y)@, where @x@ and @y@ are non-negative integers.-module Math.NumberTheory.Pell ( - Solution,- solve ) where+module Math.NumberTheory.Pell+ ( Solution+ , solve+ ) where -import Control.Arrow ((***))-import Data.List (sort, nub)-import Data.Ratio ((%))-import Data.Set (toList)-import Math.NumberTheory.Moduli.SquareRoots (sqrts)-import Math.NumberTheory.Pell.PQa (PQa(..), period)-import Math.NumberTheory.Powers.Squares (isSquare, integerSquareRoot)-import Math.NumberTheory.Primes.Factorisation (divisors)- +import Control.Arrow ((***))+import Data.List (sort, nub)+import Data.Ratio ((%))+import Data.Set (toList)+import Math.NumberTheory.Moduli.SquareRoots (sqrts)+import Math.NumberTheory.Pell.PQa (PQa(..), period)+import Math.NumberTheory.Powers.Squares (isSquare, integerSquareRoot)+import Math.NumberTheory.ArithmeticFunctions (divisors)+ fmzs :: Integer -> Integer -> [(Integer, Integer, [Integer])] fmzs d n = map (\f -> let m = n `div` (f * f) in (f, m, zs m)) $ filter (\f -> (n `mod` (f * f)) == 0) $ toList $ divisors n where @@ -36,12 +37,12 @@ am = abs m am2 = floor (am % 2) norm x = if x <= am2 then x else x - am- + getRS :: Integer -> Integer -> Integer -> Maybe (Integer, Integer)-getRS d m z = +getRS d m z = let (_, pqas) = period z (abs m) d- qrs = zipWith (\x y -> (q x, g y, b y)) (tail pqas) pqas + qrs = zipWith (\x y -> (q x, g y, b y)) (tail pqas) pqas rss = map (\(_, r, s) -> (r, s)) $ filter (\(q', _, _) -> abs q' == 1) qrs in case rss of@@ -99,15 +100,15 @@ toMinimal (x, y) = minimum $ map (abs *** abs) $ filter (\(x', y') -> x' * y' >= 0) [(x, y), mul d (r, s) (x, y), mul d (r, -s) (x, y)] -- |@solve d n@ calculates all non-negative integer solutions of the generalized Pell Equation--- x^2 - @d@y^2 = @n@, +-- x^2 - @d@y^2 = @n@, -- where @d@ must be a positive integer which is not a square, -- and @n@ must be a non-zero integer. solve :: Integer -> Integer -> [Solution]-solve d n +solve d n | d <= 0 = error $ "D must be positive, but D == " ++ show d ++ "." | isSquare d = error $ "D must not be a square, but D == " ++ show (integerSquareRoot d) ++ "^2." | n == 0 = error "N must not be zero."- | otherwise = case getMinimalReps d n of + | otherwise = case getMinimalReps d n of (_, []) -> [] ((r, s), xys) -> go xys where go xys' = normalize xys' ++ go (step xys')
Math/NumberTheory/Pell/PQa.hs view
@@ -1,27 +1,29 @@-module Math.NumberTheory.Pell.PQa (- PQa(..),- pqa,- reduced, - period) where+module Math.NumberTheory.Pell.PQa+ ( PQa(..)+ , pqa+ , reduced+ , period+ ) where -import Data.Ratio ((%))+import Data.Ratio ((%)) import Math.NumberTheory.Powers.Squares (isSquare, integerSquareRoot) -data PQa = PQa {- a :: Integer,- b :: Integer,- g :: Integer,- a' :: Integer,- p :: Integer,- q :: Integer } deriving Show- +data PQa = PQa+ { a :: Integer+ , b :: Integer+ , g :: Integer+ , a' :: Integer+ , p :: Integer+ , q :: Integer+ } deriving Show+ pqa :: Integer -> Integer -> Integer -> [PQa] pqa p0 q0 d | q0 == 0 = error "Q0 must not be zero." | d <= 0 = error "D must be positive." | isSquare d = error $ "D must not be a square, but D == " ++ show dd ++ "^2."- | (p0 * p0 - d) `mod` q0 /= 0 = error $ "P0^2 must be equivalent to D modulo Q0, but " - ++ show p0 ++ "^2 == " ++ show (p0 `mod` q0) ++ " /= " ++ show (d `mod` q0) + | (p0 * p0 - d) `mod` q0 /= 0 = error $ "P0^2 must be equivalent to D modulo Q0, but "+ ++ show p0 ++ "^2 == " ++ show (p0 `mod` q0) ++ " /= " ++ show (d `mod` q0) ++ " == " ++ show d ++ " (mod " ++ show q0 ++ ")" | otherwise = go p0 q0 (PQa 0 1 (-p0) undefined undefined undefined) (PQa 1 0 q0 undefined undefined undefined) where@@ -43,7 +45,7 @@ reduced x y dd | y > 0 = (dd >= y - x) && (dd < x + y) && (dd >= x) | otherwise = (dd < y - x) && (dd >= x + y) && (dd < x)- + period :: Integer -> Integer -> Integer -> (Int, [PQa]) period p0 q0 d = u [] 0 $ pqa p0 q0 d where dd = integerSquareRoot d
Math/NumberTheory/Pell/Test.hs view
@@ -1,35 +1,21 @@ module Math.NumberTheory.Pell.Test where -import Distribution.TestSuite.QuickCheck (Test, testProperty, testGroup)+import Distribution.TestSuite.QuickCheck (Test, testProperty, testGroup) import Math.NumberTheory.Moduli.SquareRoots.Test (prop_sqrtsPP, prop_sqrts)-import Math.NumberTheory.Pell.Test.Reduced (prop_reduced)-import Math.NumberTheory.Pell.Test.Solve (Problem (..), prop_solves)+import Math.NumberTheory.Pell.Test.Reduced (prop_reduced)+import Math.NumberTheory.Pell.Test.Solve (Problem (..), prop_solves) tests :: IO [Test]-tests = return - [- testGroup "SquareRoots"- [- testProperty "sqrtsPP" prop_sqrtsPP,- testProperty "sqrts" prop_sqrts- ],- testGroup "Pell"- [- testProperty "reduced" prop_reduced,- testProperty "solves 7 9" (prop_solves 100 $ Problem 7 9),- testProperty "solves 5 (-4)" (prop_solves 100 $ Problem 5 (-4)),- testProperty "solves 2 (-7)" (prop_solves 100 $ Problem 2 (-7)),- testProperty "solves" (prop_solves 100000)- ]- ]---- main :: IO ()--- main = do--- test prop_sqrtsPP--- test prop_sqrts--- test prop_reduced--- test (prop_solves 100 $ Problem 7 9)--- test (prop_solves 100 $ Problem 5 (-4))--- test (prop_solves 100 $ Problem 2 (-7))--- test (prop_solves 100000)---+tests = return+ [ testGroup "SquareRoots"+ [ testProperty "sqrtsPP" prop_sqrtsPP+ , testProperty "sqrts" prop_sqrts+ ]+ , testGroup "Pell"+ [ testProperty "reduced" prop_reduced+ , testProperty "solves 7 9" (prop_solves 100 $ Problem 7 9)+ , testProperty "solves 5 (-4)" (prop_solves 100 $ Problem 5 (-4))+ , testProperty "solves 2 (-7)" (prop_solves 100 $ Problem 2 (-7))+ , testProperty "solves" (prop_solves 100000)+ ]+ ]
Math/NumberTheory/Pell/Test/Reduced.hs view
@@ -1,9 +1,11 @@-module Math.NumberTheory.Pell.Test.Reduced ( prop_reduced ) where+module Math.NumberTheory.Pell.Test.Reduced+ ( prop_reduced+ ) where -import Math.NumberTheory.Pell.PQa (reduced)+import Math.NumberTheory.Pell.PQa (reduced) import Math.NumberTheory.Powers.Squares (isSquare, integerSquareRoot) import Test.QuickCheck- + data Triple = Triple Integer Integer Integer deriving (Show, Eq) isProperTriple :: Triple -> Bool@@ -19,27 +21,27 @@ y = (pp - dd) / qq in (x, y)- + isReduced :: Triple -> Bool isReduced t = let (x, y) = toDouble t in (x > 1) && (-1 < y) && (y < 0)- + genTriple :: Gen Triple genTriple = flip suchThat isProperTriple $ do p <- scale (* 2) arbitrary q <- scale (* 2) arbitrary d <- scale (* 3) arbitrary return $ Triple p q d- + instance Arbitrary Triple where arbitrary = oneof $ map (suchThat genTriple) [isReduced, not . isReduced] shrink (Triple p q d) = filter isProperTriple $ [Triple p' q d | p' <- shrink p] ++ [Triple p q' d | q' <- shrink q] ++ [Triple p q d' | d' <- shrink d]- + reduced' :: Triple -> Bool reduced' (Triple p q d) = reduced p q (integerSquareRoot d)- + prop_reduced :: Triple -> Property prop_reduced t@(Triple _ _ d) = counterexample (show $ toDouble t) $@@ -48,4 +50,4 @@ classify (d <= 100) "d <= 100" $ classify (d > 100) "d > 100" $ reduced' t === isReduced t- +
Math/NumberTheory/Pell/Test/Solve.hs view
@@ -1,10 +1,11 @@-module Math.NumberTheory.Pell.Test.Solve (- Problem (..),- prop_solves,- naive) where+module Math.NumberTheory.Pell.Test.Solve+ ( Problem (..)+ , prop_solves+ , naive+ ) where -import Control.Monad (liftM2)-import Math.NumberTheory.Pell (solve)+import Control.Monad (liftM2)+import Math.NumberTheory.Pell (solve) import Math.NumberTheory.Powers.Squares (isSquare, integerSquareRoot) import Test.QuickCheck @@ -27,21 +28,21 @@ x <- suchThat arbitrary (> 0) let y = integerSquareRoot x elements [-y, y]- + shrinkN :: Integer -> [Integer] shrinkN n = filter (/= 0) $ shrink n- + instance Arbitrary Problem where arbitrary = liftM2 Problem genD genN shrink (Problem d n) = [Problem d' n | d' <- shrinkD d] ++ [Problem d n' | n' <- shrinkN n]- + naive :: Integer -> Integer -> Integer -> [(Integer, Integer)]-naive maxY d n = [(integerSquareRoot $ n + d * y * y, y) | y <- [0..maxY], isSquare $ n + d * y * y] +naive maxY d n = [(integerSquareRoot $ n + d * y * y, y) | y <- [0..maxY], isSquare $ n + d * y * y] prop_solves :: Integer -> Problem -> Property prop_solves limit (Problem d n) = classify (n == 1) "n == 1" $- classify (n == (-1)) "n == -1" $ + classify (n == (-1)) "n == -1" $ classify (n == 4) "n == 4" $ classify (n == (-4)) "n == -4" $ classify (abs n `notElem` [1, 4]) "|n| /= 1, 4" $
Math/NumberTheory/Pell/Test/Utils.hs view
@@ -1,5 +1,6 @@-module Math.NumberTheory.Pell.Test.Utils (- (~~) ) where+module Math.NumberTheory.Pell.Test.Utils+ ( (~~)+ ) where import Test.QuickCheck
− dist/build/test-pellStub/test-pellStub-tmp/test-pellStub.hs
@@ -1,5 +0,0 @@-module Main ( main ) where-import Distribution.Simple.Test.LibV09 ( stubMain )-import Math.NumberTheory.Pell.Test ( tests )-main :: IO ()-main = stubMain tests
pell.cabal view
@@ -2,47 +2,46 @@ -- see http://haskell.org/cabal/users-guide/ name: pell-version: 0.1.0.0+version: 0.1.1.0 synopsis: Package to solve the Generalized Pell Equation. description: Finds all solutions of the generalized Pell Equation. homepage: https://github.com/brunjlar/pell license: MIT license-file: LICENSE author: Lars Bruenjes-maintainer: lbrunjes@gmx.de-copyright: (c) 2015 by Dr. Lars Brünjes +maintainer: brunjlar@gmail.com+copyright: (c) 2016 by Dr. Lars Brünjes category: Math, Algorithms, Number Theory build-type: Simple extra-source-files: README.md cabal-version: >=1.20.0 library- exposed-modules: Math.NumberTheory.Pell, Math.NumberTheory.Moduli.SquareRoots+ exposed-modules: Math.NumberTheory.Pell+ , Math.NumberTheory.Moduli.SquareRoots other-modules: Math.NumberTheory.Pell.PQa- -- other-extensions: - build-depends: base >=4.7 && <4.8, - arithmoi, - containers- -- hs-source-dirs: + build-depends: base >=4.7 && <5+ , arithmoi+ , containers default-language: Haskell2010 Test-Suite test-pell type: detailed-0.9 test-module: Math.NumberTheory.Pell.Test- other-modules: Math.NumberTheory.Moduli.SquareRoots,- Math.NumberTheory.Moduli.SquareRoots.Test,- Math.NumberTheory.Pell,- Math.NumberTheory.Pell.PQa,- Math.NumberTheory.Pell.Test.Reduced,- Math.NumberTheory.Pell.Test.Solve,- Math.NumberTheory.Pell.Test.Utils- build-depends: base >= 4.7 && <4.8, - arithmoi, - containers, - QuickCheck >= 2.8, - primes, - Cabal >= 1.20.0,- cabal-test-quickcheck+ other-modules: Math.NumberTheory.Moduli.SquareRoots+ , Math.NumberTheory.Moduli.SquareRoots.Test+ , Math.NumberTheory.Pell+ , Math.NumberTheory.Pell.PQa+ , Math.NumberTheory.Pell.Test.Reduced+ , Math.NumberTheory.Pell.Test.Solve+ , Math.NumberTheory.Pell.Test.Utils+ build-depends: base >= 4.7 && <5+ , arithmoi+ , containers+ , QuickCheck >= 2.8+ , primes+ , Cabal >= 1.20.0+ , cabal-test-quickcheck default-language: Haskell2010 source-repository head@@ -52,4 +51,4 @@ source-repository this type: git location: https://github.com/brunjlar/pell- tag: 0.1.0.0+ tag: 0.1.1.0