# integer-roots

Integer roots and perfect powers

https://github.com/Bodigrim/integer-roots

 LTS Haskell 21.24: 1.0.2.0@rev:1 Stackage Nightly 2023-12-09: 1.0.2.0@rev:1 Latest on Hackage: 1.0.2.0@rev:1

See all snapshots `integer-roots` appears in

Maintained by
This version can be pinned in stack with:`integer-roots-1.0.2.0@sha256:67a8b36c783337cb9f51a83adfc657eb8d7724a12c7b3ba186ba70ff7ce2c3b9,2476`

#### Module documentation for 1.0.2.0

• Math
• Math.NumberTheory
Depends on 2 packages(full list with versions):
Used by 2 packages in nightly-2023-12-09(full list with versions):

# integer-roots   Calculating integer roots and testing perfect powers of arbitrary precision.

## Integer square root

The integer square root (`integerSquareRoot`) of a non-negative integer n is the greatest integer m such that . Alternatively, in terms of the floor function, .

For example,

``````> integerSquareRoot 99
9
> integerSquareRoot 101
10
``````

It is tempting to implement `integerSquareRoot` via `sqrt :: Double -> Double`:

``````integerSquareRoot :: Integer -> Integer
integerSquareRoot = truncate . sqrt . fromInteger
``````

However, this implementation is faulty:

``````> integerSquareRoot (3037000502^2)
3037000501
> integerSquareRoot (2^1024) == 2^1024
True
``````

The problem here is that `Double` can represent only a limited subset of integers without precision loss. Once we encounter larger integers, we lose precision and obtain all kinds of wrong results.

This library features a polymorphic, efficient and robust routine `integerSquareRoot :: Integral a => a -> a`, which computes integer square roots by Karatsuba square root algorithm without intermediate `Double`s.

## Integer cube roots

The integer cube root (`integerCubeRoot`) of an integer n equals to .

Again, a naive approach is to implement `integerCubeRoot` via `Double`-typed computations:

``````integerCubeRoot :: Integer -> Integer
integerCubeRoot = truncate . (** (1/3)) . fromInteger
``````

Here the precision loss is even worse than for `integerSquareRoot`:

``````> integerCubeRoot (4^3)
3
> integerCubeRoot (5^3)
4
``````

That is why we provide a robust implementation of `integerCubeRoot :: Integral a => a -> a`, which computes roots by generalized Heron algorithm.

## Higher powers

In spirit of `integerSquareRoot` and `integerCubeRoot` this library covers the general case as well, providing `integerRoot :: (Integral a, Integral b) => b -> a -> a` to compute integer k-th roots of arbitrary precision.

There is also `highestPower` routine, which tries hard to represent its input as a power with as large exponent as possible. This is a useful function in number theory, e. g., elliptic curve factorisation.

``````> map highestPower [2..10]
[(2,1),(3,1),(2,2),(5,1),(6,1),(7,1),(2,3),(3,2),(10,1)]
``````

# 1.0.2.0

• More fixes for big-endian architectures.

# 1.0.1.0

• Fixes for big-endian architectures.

# 1.0.0.1

• Compatibility fixes for GHC 9.2.

# 1.0

• Initial release.