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.

[Skip to Readme]
Versions [faq] 1.0
Change log
Dependencies base (>=4.9 && <5), integer-gmp (<1.1) [details]
License MIT
Copyright (c) 2011 Daniel Fischer, 2016-2020 Andrew Lelechenko.
Author Daniel Fischer, Andrew Lelechenko
Maintainer Andrew Lelechenko andrew dot lelechenko at gmail dot com
Category Math, Algorithms, Number Theory
Home page
Bug tracker
Source repo head: git clone
Uploaded by Bodigrim at 2020-02-08T18:09:09Z
Distributions NixOS:1.0
Downloads 734 total (64 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Hackage Matrix CI
Docs available [build log]
Last success reported on 2020-02-08 [all 1 reports]


[Index] [Quick Jump]


Maintainer's Corner

For package maintainers and hackage trustees

Readme for integer-roots-1.0

[back to package description]

integer-roots Build Status Hackage Hackage CI Stackage LTS Stackage Nightly

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 <img src="\le\sqrt{n}">. Alternatively, in terms of the floor function, <img src=" = \lfloor\sqrt{n}\rfloor">.

For example,

> integerSquareRoot 99
> integerSquareRoot 101

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)
> isqrt (2^1024) == 2^1024

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 <img src="\lfloor\sqrt[3]{n}\rfloor">.

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)
> integerCubeRoot (5^3)

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]