Package de.tilman_neumann.jml.roots
Class Roots
java.lang.Object
de.tilman_neumann.jml.roots.Roots
public class Roots
extends java.lang.Object
i.th root of integers.
The current state-of-the-art is a Heron-style algorithm with a good initial guess derived from double computations.
For very small
ld(N)/i
a linear algorithm is applied.
The Heron-style algorithm realizes the iteration formula x(k+1) = 1/n * ( (n-1) * x(k) + N/(x(k)^(n-1)) ),
see {@link "https://en.wikipedia.org/wiki/Nth_root_algorithm"}.
Thanks to Graeme Willoughby to point my nose to that algorithm.-
Constructor Summary
Constructors Constructor Description Roots()
-
Method Summary
Modifier and Type Method Description static java.math.BigInteger[]
ithRoot(java.math.BigInteger N, int i)
Computes the i.th root of N, using either a bitwise correction approach (for rather big rootsi
) or a Heron iteration procedure (for rather small rootsi
).static java.math.BigInteger[]
ithRoot_Heron1(java.math.BigInteger N, int i)
Heron-style i.th root implementation.static java.math.BigInteger[]
ithRoot_Heron2(java.math.BigInteger N, int i)
Heron-style i.th root implementation.static void
main(java.lang.String[] args)
Test.Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
-
Constructor Details
-
Roots
public Roots()
-
-
Method Details
-
ithRoot
public static java.math.BigInteger[] ithRoot(java.math.BigInteger N, int i)Computes the i.th root of N, using either a bitwise correction approach (for rather big rootsi
) or a Heron iteration procedure (for rather small rootsi
). The decision point between the two algorithms is heuristic and may not be very accurate.- Parameters:
N
- argumenti
- root- Returns:
- [lower, upper] integer bounds of i.th root of N
-
ithRoot_Heron1
public static java.math.BigInteger[] ithRoot_Heron1(java.math.BigInteger N, int i)Heron-style i.th root implementation. This algorithm is much faster than the bitwise correction except forld(N)/i <= 2
. Notes: 1. We use a good initial guess based on double computations. 2. The main loop could have convergence problems for smallld(N)/i
; but in these cases the initial guess is very good! Testing the initial guess before the main loop solves the problem. 3. Doing an additional iteration step before the main loop does not pay out. Version 1 is sure to give the correct result because of the final step doing a loop.- Parameters:
N
-i
-- Returns:
- [lower, upper] int values of i.th root(N)
-
ithRoot_Heron2
public static java.math.BigInteger[] ithRoot_Heron2(java.math.BigInteger N, int i)Heron-style i.th root implementation. This algorithm is much faster than the bitwise correction except forld(N)/i <= 2
. Notes: 1. We use a good initial guess based on double computations. 2. The main loop could have convergence problems for smallld(N)/i
; but in these cases the initial guess is very good! Testing the initial guess before the main loop solves the problem. 3. Doing an additional iteration step before the main loop does not pay out. This implementation differs from version 1 as follows: 4. Following {@link "https://en.wikipedia.org/wiki/Nth_root_algorithm"} we dodelta(k) = 1/n * [N/x(k)^(n-1) - x(k)]; x(k+1) = x(k)+delta(k)
. 5. The above allows for a simpler convergence check. 6. The final step exploits that the guess after the main loop does not differ from the correct result by more than 1.- Parameters:
N
-i
-- Returns:
- [lower, upper] int values of i.th root(N)
-
main
public static void main(java.lang.String[] args)Test.- Parameters:
args
- ignored
-