Newton's method with the given digits of accuracy

Question

I am trying to write a function in Java that calculates the nth root of a number. For this, I use Newton's method. However, the user should be able to specify how many precision digits they want. This is the part that I'm having problems with, since my answer is often not entirely correct. The relevant code is here: http://pastebin.com/d3rdpLW8 . How can I fix this code so that it always gives an answer of at least p digits of accuracy? (without doing more work than necessary)

import java.util.Random;

public final class Compute {

    private Compute() {
    }

    public static void main(String[] args) {
        Random rand = new Random(1230);
        for (int i = 0; i < 500000; i++) {
            double k = rand.nextDouble()/100;
            int n = (int)(rand.nextDouble() * 20) + 1;
            int p = (int)(rand.nextDouble() * 10) + 1;
            double math = n == 0 ? 1d : Math.pow(k, 1d / n);
            double compute = Compute.root(n, k, p);
            if(!String.format("%."+p+"f", math).equals(String.format("%."+p+"f", compute))) {
                System.out.println(String.format("%."+p+"f", math));
                System.out.println(String.format("%."+p+"f", compute));
                System.out.println(math + " " + compute + " " + p);
            }
        }
    }

    /**
     * Returns the n-th root of a positive double k, accurate to p decimal
     * digits.
     * 
     * @param n
     *            the degree of the root.
     * @param k
     *            the number to be rooted.
     * @param p
     *            the decimal digit precision.
     * @return the n-th root of k
     */
    public static double root(int n, double k, int p) {     
        double epsilon = pow(0.1, p+2);
        double approx = estimate_root(n, k);
        double approx_prev;

        do {
            approx_prev = approx;
            // f(x) / f'(x) = (x^n - k) / (n * x^(n-1)) = (x - k/x^(n-1)) / n
            approx -= (approx - k / pow(approx, n-1)) / n;
        } while (abs(approx - approx_prev) > epsilon);
        return approx;
    }

    private static double pow(double x, int y) {
        if (y == 0)
            return 1d;
        if (y == 1)
            return x;
        double k = pow(x * x, y >> 1);
        return (y & 1) == 0 ? k : k * x;
    }

    private static double abs(double x) {
        return Double.longBitsToDouble((Double.doubleToLongBits(x) << 1) >>> 1);
    }

    private static double estimate_root(int n, double k) {
        // Extract the exponent from k.
        long exp = (Double.doubleToLongBits(k) & 0x7ff0000000000000L);
        // Format the exponent properly.
        int D = (int) ((exp >> 52) - 1023);
        // Calculate and return 2^(D/n).
        return Double.longBitsToDouble((D / n + 1023L) << 52);
    }
}

Answer 1

Just try again until the update is less than 0.0001 if you need 4 decimal places precision.

, epsilon Math.pow(10, -n), n .

Answer 2

, . , n- n- .

, , ? , e (0). e (0), , .

, "e (0) <= m". n , e (n) <= k k. f '' , ( ) , x.

, , - k, . , . , , , , .

Answer 3

You have a bug in the code. Your last line pow()should read
return (y & 1) == 1 ? k : k * x;
and not return (y & 1) == 0 ? k : k * x;