Safe Haskell	Safe-Inferred
Language	Haskell2010

Math.Combinat.Numbers.Integers

Contents

Integer logarithm
Integer square root

Description

Operations on integers

Synopsis

integerLog2 :: Integer -> Integer
ceilingLog2 :: Integer -> Integer
isSquare :: Integer -> Bool
integerSquareRoot :: Integer -> Integer
ceilingSquareRoot :: Integer -> Integer
integerSquareRoot' :: Integer -> (Integer, Integer)
integerSquareRootNewton' :: Integer -> (Integer, Integer)

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

isSquare :: Integer -> Bool Source #

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.