Package de.tilman_neumann.jml.roots

Class Roots

  • public class Roots
extends 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.
    Author:
    Tilman Neumann

    • Constructor Detail

      • Roots

        public Roots()

    • Method Detail

      • ithRoot

        public static BigInteger[] ithRoot​(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 BigInteger[] ithRoot_Heron1​(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 BigInteger[] ithRoot_Heron2​(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​(String[] args)
        Test.
        Parameters:
        args - ignored