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 roots i) or a Heron iteration procedure (for rather small roots i).
    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 roots i) or a Heron iteration procedure (for rather small roots i). The decision point between the two algorithms is heuristic and may not be very accurate.
      Parameters:
      N - argument
      i - 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 for ld(N)/i <= 2 .

      Notes:
      1. We use a good initial guess based on double computations.
      2. The main loop could have convergence problems for small ld(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 for ld(N)/i <= 2 .

      Notes:
      1. We use a good initial guess based on double computations.
      2. The main loop could have convergence problems for small ld(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 do delta(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