# integer-roots: Integer roots and perfect powers

[ algorithms, library, math, mit, number-theory ] [ Propose Tags ]

Calculating integer roots and testing perfect powers of arbitrary precision. Originally part of arithmoi package.

## Modules

[Index] [Quick Jump]

#### Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees

Candidates

• No Candidates
Versions [RSS] 1.0, 1.0.0.1, 1.0.1.0, 1.0.2.0 changelog.md base (>=4.9 && <5), ghc-bignum (<1.3), integer-gmp (<1.2) [details] MIT (c) 2011 Daniel Fischer, 2016-2021 Andrew Lelechenko. Daniel Fischer, Andrew Lelechenko Andrew Lelechenko andrew dot lelechenko at gmail dot com Math, Algorithms, Number Theory https://github.com/Bodigrim/integer-roots https://github.com/Bodigrim/integer-roots/issues head: git clone https://github.com/Bodigrim/integer-roots by Bodigrim at 2021-11-22T20:09:13Z Arch:1.0.2.0, LTSHaskell:1.0.2.0, NixOS:1.0.2.0 5 direct, 7089 indirect [details] 3560 total (100 in the last 30 days) (no votes yet) [estimated by Bayesian average] λ λ λ Docs available Last success reported on 2021-11-22

[back to package description]

# 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 Doubles.

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