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.0.1.tar.gz [browse] (Cabal source package)
- Package description (as included in the package)
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 && <5), 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 |
| 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-08-23T19:18:05Z |
| 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, 7741 indirect [details] |
| Downloads | 4236 total (54 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-08-23 [all 1 reports] |
Readme for integer-roots-1.0.0.1
[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)]