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]

Modules

[Index] [Quick Jump]

Downloads

Note: This package has metadata revisions in the cabal description newer than included in the tarball. To unpack the package including the revisions, use 'cabal get'.

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
Change log changelog.md
Dependencies base (>=4.9 && <5), ghc-bignum (<1.4), integer-gmp (<1.2) [details]
License MIT
Copyright (c) 2011 Daniel Fischer, 2016-2021 Andrew Lelechenko.
Author Daniel Fischer, Andrew Lelechenko
Maintainer Andrew Lelechenko andrew dot lelechenko at gmail dot com
Revised Revision 1 made by Bodigrim at 2023-04-15T00:50:37Z
Category Math, Algorithms, Number Theory
Home page https://github.com/Bodigrim/integer-roots
Bug tracker https://github.com/Bodigrim/integer-roots/issues
Source repo head: git clone https://github.com/Bodigrim/integer-roots
Uploaded by Bodigrim at 2021-11-22T20:09:13Z
Distributions Arch:1.0.2.0, LTSHaskell:1.0.2.0, NixOS:1.0.2.0, Stackage:1.0.2.0
Reverse Dependencies 5 direct, 7432 indirect [details]
Downloads 3962 total (71 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Docs available [build log]
Last success reported on 2021-11-22 [all 1 reports]

Readme for integer-roots-1.0.2.0

[back to package description]

integer-roots Hackage 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 . 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)]