combinat-0.2.9.0: Generate and manipulate various combinatorial objects.

Math.Combinat.Numbers.Integers

Description

Operations on integers

Synopsis

# Integer logarithm

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

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

# Integer square root

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.

Smallest integer whose square is larger or equal to the input

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)

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