Using an array of precomputed powers to extract roots

Question

I am writing a program that solves a sum of tenth powers problem and I need to have a fast algorithm to find n^10 as well as n^(1/10) For natural n<1 000 000. I am precomputing an array of powers, so n^10 (array lookup) takes O(1). For n^(1/10) I am doing a binary search. Is there any way to accelerate extraction of a root beyond that? For example, making an array and filling elements with corresponding roots if the index is a perfect power or leaving zero otherwise would give O(1), but I will run out of memory. Is there a way to make root extraction faster than O(log(n))?

Answer 1

Why should the array of roots run out of memory? If it is the same size as the array of powers, it will fit using the same datatypes. However for the powers, (10^6)^10 = 10^60, which does not fit into a long variable so you need to use biginteger or bigdecimal types. In case your number n is bigger than the biggest array size n_max your memory can afford, you can divide n by n_m until it fits, i.e. split n = n_max^m*k, where m is a natural number and k < n_max:

public class Roots
{
    static final int N_MAX = 1_000_000;

    double[] roots = new double[N_MAX+1];

    Roots() {for (int i = 0; i <= N_MAX; i++) {roots[i] = Math.pow(i, 0.1);}}

    double root(long n)
    {
        int m = 0;
        while (n > N_MAX)
        {
            n /= N_MAX;
            m++;
        }
        return (Math.pow(roots[N_MAX],m)*roots[(int)n]); // in a real case you would precompute pow(roots[N_MAX],m) as well
    }

    static public void main(String[] args)
    {
        Roots root = new Roots();
        System.out.println(root.root(1000));
        System.out.println(root.root(100_000_000_000_000l));
    }
}

Answer 2

Apart LUT You got two options to speed up I can think of:

1. use binary search without multiplication

   If you are using bignums then 10th-root binary search search is not O(log(n)) anymore as the basic operation used in it are no longer O(1) !!! For example +,-,<<,>>,|,&,^,>=,<=,>,<,==,!= will became O(b) and * will be O(b^2) or O(b.log(b)) where b=log(n) depending on algorithm used (or even operand magnitude). So naive binary search for root finding will be in the better case O(log^2(n).log(log(n)))

   To speedup it you can try not to use multiplication. Yes it is possible and the final complexity will bee O(log^2(n)) Take a look at:

   • How to get a square root for 32 bit input in one clock cycle only?

   To see how to achieve this. The difference is only in solving different equations:

   x1 = x0+m
   x1^10 = f(x0,m)
   

   If you obtain algebraically x1=f(x0,m) then each multiplication inside translate to bit-shifts and adds... For example 10*x = x<<1 + x<<3. The LUT table is not necessary as you can iterate it during binary search. I imagine that f(x0,m) will contain lesser powers of x0 so analogically compute all the needed powers too ... so the final result will have no powering. Sorry too lazy to do that for you, you can use some math app for that like Derive for Windows

2. you can use pow(x,y) = x^y = exp2(y*log2(x))

   So x^0.1 = exp2(log2(x)/10) But you would need bigdecimals for this (or fixed point) here see how I do it:

   • How can I write a power function myself?

For more ideas see this:

• Power by squaring for negative exponents