h${    (c) 2019 Andrew LelechenkoMIT/Andrew Lelechenko None 4(c) 2011 Daniel Fischer, 2016-2020 Andrew LelechenkoMIT/Andrew Lelechenko None2 (c) 2020 Andrew LelechenkoMIT/Andrew Lelechenko None4(c) 2011 Daniel Fischer, 2016-2020 Andrew LelechenkoMIT1Daniel Fischer None Z integer-rootsFor a non-negative input  n & calculate its integer square root  \lfloor \sqrt{n} \rfloor &. Throw an error on negative input.integerSquareRoot 999integerSquareRoot 10010integerSquareRoot 10110 integer-roots;Calculate the integer square root of a non-negative number n", that is, the largest integer r with r*r <= n. The precondition n >= 0 is not checked. integer-rootsFor a non-negative input  n & calculate its integer square root  r = \lfloor \sqrt{n} \rfloor  and remainder  s = n - r^2 &. Throw an error on negative input.integerSquareRootRem 99(9,18)integerSquareRootRem 100(10,0)integerSquareRootRem 101(10,1) integer-rootsCalculate the integer square root of a non-negative number as well as the difference of that number with the square of that root, that is if (s,r) = integerSquareRootRem' n then s^2 <= n == s^2+r < (s+1)^2. The precondition n >= 0 is not checked. integer-rootsCalculate the exact integer square root if it exists, otherwise return .(map exactSquareRoot [-100, 99, 100, 101]![Nothing,Nothing,Just 10,Nothing] integer-roots.Test whether the argument is a perfect square.!map isSquare [-100, 99, 100, 101][False,False,True,False] integer-roots/Test whether the input (a non-negative number) n is a square. The same as , but without the negativity test. Faster if many known positive numbers are tested.The precondition n >= 0 is not tested, passing negative arguments may cause any kind of havoc. integer-rootsTest whether a non-negative number may be a square. Non-negativity is not checked, passing negative arguments may cause any kind of havoc.First the remainder modulo 256 is checked (that can be calculated easily without division and eliminates about 82% of all numbers). After that, the remainders modulo 9, 25, 7, 11 and 13 are tested to eliminate altogether about 99.436% of all numbers.4(c) 2011 Daniel Fischer, 2016-2020 Andrew LelechenkoMIT1Daniel Fischer None integer-rootsCalculate the integer fourth root of a nonnegative number, that is, the largest integer r with r^4 <= n'. Throws an error on negaitve input. integer-rootsCalculate the integer fourth root of a nonnegative number, that is, the largest integer r with r^4 <= n. The condition is not checked. integer-rootsReturns Nothing if n is not a fourth power, Just r if n == r^4 and r >= 0. integer-rootsTest whether an integer is a fourth power. First nonnegativity is checked, then the unchecked test is called. integer-rootsTest whether a nonnegative number is a fourth power. The condition is not$ checked. If a number passes the 0 test, its integer fourth root is calculated. integer-rootsTest whether a nonnegative number is a possible fourth power. The condition is not6 checked. This eliminates about 99.958% of numbers.4(c) 2011 Daniel Fischer, 2016-2020 Andrew LelechenkoMIT1Daniel Fischer None integer-roots For a given  n $ calculate its integer cube root  \lfloor \sqrt[3]{n} \rfloor -. Note that this is not symmetric about 0.map integerCubeRoot [7, 8, 9][1,2,2] map integerCubeRoot [-7, -8, -9] [-2,-2,-3] integer-roots9Calculate the integer cube root of a nonnegative integer n", that is, the largest integer r such that r^3 <= n. The precondition n >= 0 is not checked. integer-rootsCalculate the exact integer cube root if it exists, otherwise return .'map exactCubeRoot [-9, -8, -7, 7, 8, 9]2[Nothing,Just (-2),Nothing,Nothing,Just 2,Nothing] integer-roots,Test whether the argument is a perfect cube. map isCube [-9, -8, -7, 7, 8, 9]#[False,True,False,False,True,False] integer-roots8Test whether a nonnegative integer is a cube. Before  is calculated, a few tests of remainders modulo small primes weed out most non-cubes. For testing many numbers, most of which aren't cubes, this is much faster than  let r = cubeRoot n in r*r*r == n. The condition n >= 0 is not checked. integer-rootsTest whether a nonnegative number is possibly a cube. Only about 0.08% of all numbers pass this test. The precondition n >= 0 is not checked.(c) 2017 Andrew LelechenkoMIT/Andrew Lelechenko  Safe-Inferred !"#$%& 4(c) 2011 Daniel Fischer, 2016-2020 Andrew LelechenkoMIT1Daniel Fischer None& integer-rootsFor a positive power  k  and a given  n  return the integer  k  -th root  \lfloor \sqrt[k]{n} \rfloor . Throw an error if  k \le 0  or if  n \le 0  and  k  is even.integerRoot 6 652integerRoot 5 2433integerRoot 4 6244integerRoot 3 (-124)-5integerRoot 1 55 integer-rootsFor a positive exponent  k  calculate the exact integer  k -th root of the second argument if it exists, otherwise return .map (uncurry exactRoot) [(6, 65), (5, 243), (4, 624), (3, -124), (1, 5)]'[Nothing,Just 3,Nothing,Nothing,Just 5] integer-rootsFor a positive exponent  k 0 test whether the second argument is a perfect  k  -th power.map (uncurry isKthPower) [(6, 65), (5, 243), (4, 624), (3, -124), (1, 5)][False,True,False,False,True]  integer-rootsTest whether the argument is a non-trivial perfect power (e. g., square, cube, etc.).map isPerfectPower [0..10]>[True,True,False,False,True,False,False,False,True,True,False]map isPerfectPower [-10..0][False,False,True,False,False,False,False,False,False,True,True]  integer-rootsFor  n \not\in \{ -1, 0, 1 \}  find the largest exponent  k  for which an exact integer  k  -th root  r  exists. Return  (r, k) .For  n \in \{ -1, 0, 1 \} = arbitrarily large exponents exist; by arbitrary convention   returns  (n, 3) .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)]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)] 4(c) 2011 Daniel Fischer, 2016-2020 Andrew LelechenkoMIT/Andrew Lelechenko None   '          !"#$%&'()*+,-./0123,integer-roots-1.0.2.0-BehDQpwSc1C3xAwidA02f0Math.NumberTheory.RootsMath.NumberTheory.Primes.Small(Math.NumberTheory.Roots.Squares.InternalMath.NumberTheory.Utils.BitMaskMath.NumberTheory.Roots.SquaresMath.NumberTheory.Roots.FourthMath.NumberTheory.Roots.Cubes$Math.NumberTheory.Utils.FromIntegralMath.NumberTheory.Roots.GeneralintegerSquareRootexactSquareRootisSquareintegerCubeRoot exactCubeRootisCube integerRoot exactRoot isKthPowerisPerfectPower highestPowersmallPrimesLengthsmallPrimesPtrisqrtA karatsubaSqrt indexBitSetintegerSquareRoot'integerSquareRootRemintegerSquareRootRem'base GHC.MaybeNothing isSquare'isPossibleSquareintegerFourthRootintegerFourthRoot'exactFourthRoot isFourthPowerisFourthPower'isPossibleFourthPowerintegerCubeRoot'isCube'isPossibleCube wordToInt wordToInteger intToWord intToIntegernaturalToIntegerintegerToNatural integerToWord integerToInt