-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Integer roots and perfect powers
--   
--   Calculating integer roots and testing perfect powers of arbitrary
--   precision. Originally part of <a>arithmoi</a> package.
@package integer-roots
@version 1.0.2.0


-- | Calculating integer roots and testing perfect powers.
module Math.NumberTheory.Roots

-- | For a non-negative input &lt;math&gt; calculate its integer square
--   root &lt;math&gt;. Throw an error on negative input.
--   
--   <pre>
--   &gt;&gt;&gt; integerSquareRoot 99
--   9
--   
--   &gt;&gt;&gt; integerSquareRoot 100
--   10
--   
--   &gt;&gt;&gt; integerSquareRoot 101
--   10
--   </pre>
integerSquareRoot :: Integral a => a -> a

-- | Test whether the argument is a perfect square.
--   
--   <pre>
--   &gt;&gt;&gt; map isSquare [-100, 99, 100, 101]
--   [False,False,True,False]
--   </pre>
isSquare :: Integral a => a -> Bool

-- | Calculate the exact integer square root if it exists, otherwise return
--   <a>Nothing</a>.
--   
--   <pre>
--   &gt;&gt;&gt; map exactSquareRoot [-100, 99, 100, 101]
--   [Nothing,Nothing,Just 10,Nothing]
--   </pre>
exactSquareRoot :: Integral a => a -> Maybe a

-- | For a given &lt;math&gt; calculate its integer cube root &lt;math&gt;.
--   Note that this is not symmetric about 0.
--   
--   <pre>
--   &gt;&gt;&gt; map integerCubeRoot [7, 8, 9]
--   [1,2,2]
--   
--   &gt;&gt;&gt; map integerCubeRoot [-7, -8, -9]
--   [-2,-2,-3]
--   </pre>
integerCubeRoot :: Integral a => a -> a

-- | Test whether the argument is a perfect cube.
--   
--   <pre>
--   &gt;&gt;&gt; map isCube [-9, -8, -7, 7, 8, 9]
--   [False,True,False,False,True,False]
--   </pre>
isCube :: Integral a => a -> Bool

-- | Calculate the exact integer cube root if it exists, otherwise return
--   <a>Nothing</a>.
--   
--   <pre>
--   &gt;&gt;&gt; map exactCubeRoot [-9, -8, -7, 7, 8, 9]
--   [Nothing,Just (-2),Nothing,Nothing,Just 2,Nothing]
--   </pre>
exactCubeRoot :: Integral a => a -> Maybe a

-- | For a positive power &lt;math&gt; and a given &lt;math&gt; return the
--   integer &lt;math&gt;-th root &lt;math&gt;. Throw an error if
--   &lt;math&gt; or if &lt;math&gt; and &lt;math&gt; is even.
--   
--   <pre>
--   &gt;&gt;&gt; integerRoot 6 65
--   2
--   
--   &gt;&gt;&gt; integerRoot 5 243
--   3
--   
--   &gt;&gt;&gt; integerRoot 4 624
--   4
--   
--   &gt;&gt;&gt; integerRoot 3 (-124)
--   -5
--   
--   &gt;&gt;&gt; integerRoot 1 5
--   5
--   </pre>
integerRoot :: (Integral a, Integral b) => b -> a -> a

-- | For a positive exponent &lt;math&gt; test whether the second argument
--   is a perfect &lt;math&gt;-th power.
--   
--   <pre>
--   &gt;&gt;&gt; map (uncurry isKthPower) [(6, 65), (5, 243), (4, 624), (3, -124), (1, 5)]
--   [False,True,False,False,True]
--   </pre>
isKthPower :: (Integral a, Integral b) => b -> a -> Bool

-- | For a positive exponent &lt;math&gt; calculate the exact integer
--   &lt;math&gt;-th root of the second argument if it exists, otherwise
--   return <a>Nothing</a>.
--   
--   <pre>
--   &gt;&gt;&gt; map (uncurry exactRoot) [(6, 65), (5, 243), (4, 624), (3, -124), (1, 5)]
--   [Nothing,Just 3,Nothing,Nothing,Just 5]
--   </pre>
exactRoot :: (Integral a, Integral b) => b -> a -> Maybe a

-- | Test whether the argument is a non-trivial perfect power (e. g.,
--   square, cube, etc.).
--   
--   <pre>
--   &gt;&gt;&gt; map isPerfectPower [0..10]
--   [True,True,False,False,True,False,False,False,True,True,False]
--   
--   &gt;&gt;&gt; map isPerfectPower [-10..0]
--   [False,False,True,False,False,False,False,False,False,True,True]
--   </pre>
isPerfectPower :: Integral a => a -> Bool

-- | For &lt;math&gt; find the largest exponent &lt;math&gt; for which an
--   exact integer &lt;math&gt;-th root &lt;math&gt; exists. Return
--   &lt;math&gt;.
--   
--   For &lt;math&gt; arbitrarily large exponents exist; by arbitrary
--   convention <a>highestPower</a> returns &lt;math&gt;.
--   
--   <pre>
--   &gt;&gt;&gt; map highestPower [0..10]
--   [(0,3),(1,3),(2,1),(3,1),(2,2),(5,1),(6,1),(7,1),(2,3),(3,2),(10,1)]
--   
--   &gt;&gt;&gt; map highestPower [-10..0]
--   [(-10,1),(-9,1),(-2,3),(-7,1),(-6,1),(-5,1),(-4,1),(-3,1),(-2,1),(-1,3),(0,3)]
--   </pre>
highestPower :: Integral a => a -> (a, Word)
