combinat-0.2.10.0: Generate and manipulate various combinatorial objects.
Safe HaskellSafe-Inferred
LanguageHaskell2010

Math.Combinat.Numbers.Integers

Description

Operations on integers

Synopsis

Integer logarithm

integerLog2 :: Integer -> Integer Source #

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

ceilingLog2 :: Integer -> Integer Source #

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

Integer square root

integerSquareRoot :: Integer -> Integer Source #

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 Source #

Smallest integer whose square is larger or equal to the input

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

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) Source #

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