Math.Combinat.Numbers.Integers

Operations on integers

Integer logarithm

integerLog2 :: Integer -> Integer

Largest integer k such that 2^k is smaller or equal to n

ceilingLog2 :: Integer -> Integer

Smallest integer k such that 2^k is larger or equal to n

Integer square root

isSquare :: Integer -> Bool

integerSquareRoot :: Integer -> Integer

Integer square root (largest integer whose square is smaller or equal to the input) using Newton's method, with a faster (for large numbers) inital guess based on bit shifts.

ceilingSquareRoot :: Integer -> Integer

Smallest integer whose square is larger or equal to the input

integerSquareRoot' :: Integer -> (Integer, Integer)

We also return the excess residue; that is

(a,r) = integerSquareRoot' n

means that

a*a + r = n
a*a <= n < (a+1)*(a+1)

integerSquareRootNewton' :: Integer -> (Integer, Integer)

Newton's method without an initial guess. For very small numbers (<10^10) it is somewhat faster than the above version.