integer-roots: Integer roots and perfect powers
Calculating integer roots and testing perfect powers of arbitrary precision. Originally part of arithmoi package.
[Skip to Readme]
Downloads
- integer-roots-1.0.tar.gz [browse] (Cabal source package)
- Package description (revised from the package)
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
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 && <4.16), integer-gmp (<1.2) [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 |
| Revised | Revision 2 made by Bodigrim at 2022-06-18T15:31:15Z |
| 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 2020-02-08T18:09:09Z |
| 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, 7735 indirect [details] |
| Downloads | 4221 total (58 in the last 30 days) |
| Rating | (no votes yet) [estimated by Bayesian average] |
| Your Rating | |
| Status | Docs available [build log] Last success reported on 2020-02-08 [all 1 reports] |
Readme for integer-roots-1.0
[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
> isqrt (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)]