Java: Performance SQRT Calculations

Question

Hi,

I have this code:

package math;

import java.io.IOException;
import java.util.Scanner;

public class Main
{
    public static void main(String[] args) throws IOException
    {
        System.out.println("Hi, I will beat Java's Math.sqrt(double) method");
        System.out.println("Both ways of calculation will be done");
        System.out.println("I will time how long they took to calculate");
        System.out.println("Random doubles will be generated");
        System.out.println();
        System.out.println("Please give the number of sqrt-calculation will be done");
        int calcs = new Scanner(System.in).nextInt();
        boolean output = true;
        if (calcs > 10000)
        {
            System.out.println("You're asking much calculations");
            System.out.println("Disabling output is recommend");
            System.out.println("Disable output? (y/n)");
            char a = (char) System.in.read();
            if (a == 'y')
            {
                output = false;
            }
        }
        System.out.println("Press enter to start");
        System.in.read();
        test(calcs, output);
        System.out.println();
        System.out.println("I was much faster I think");
        System.out.println("Now you can check my precision");
        System.out.println("Please give a complex double");
        double x = Double.parseDouble(new Scanner(System.in).next());
        System.out.println();
        System.out.println("Math.sqrt(" + x + ")           = " + Math.sqrt(x));
        System.out.println("SqrtCalculator.sqrt(" + x + ") = " + sqrt(x));
        System.out.println("------------------------");
        System.out.println("Now please make your conclusion");
        System.out.println("Thanks for trying");
    }

    public static void test(int calculations, boolean output)
    {
        double factor = Math.random() / 2;
        // Math
        long mathStart = System.currentTimeMillis();
        for (int i = 1; i <= calculations; i++)
        {
            double x = i * factor;
            double result = Math.sqrt(x);
            if (output)
            {
                System.out.println("Math.sqrt(" + x + ") =  " + result);
            }
        }
        long mathStop = System.currentTimeMillis();
        long mathTime = mathStop - mathStart;
        // My Method
        long myStart = System.currentTimeMillis();
        for (int i = 1; i <= calculations; i++)
        {
            double x = i * factor;
            double result = sqrt(x);
            if (output)
            {
                System.out.println("SqrtCalculater.sqrt(" + x + ") =  " + result);
            }
        }
        long myStop = System.currentTimeMillis();
        long myTime = myStop - myStart;
        System.out.println();
        if (output)
            System.out.println("---------------------------");
        System.out.println("Here are the results:");
        System.out.println("Math and SqrtCalculator did each " + calculations + " of the same sqrt-calculations");
        System.out.println();
        System.out.println("Math: " + mathTime + " milliseconds");
        System.out.println("I:    " + myTime + " milliseconds");
    }

    public final static double sqrt(double x)
    {
        double previous = 1;
        double now = 0;
        for (;;)
        {
            now = (x / previous + previous) / 2;
            if (previous == now)
            {
                return now;
            }
            previous = now;
        }
    }
}

This sqrt method is called "heroon".
If I run my program and I ask 80000 calculations and I disable the output, Math.sqrt() is much faster than my method. If I ask 80000 calcs and I enable the output, My method is much faster.

Can someone explain this?

Thanks

Sorry for bad English.

Answer 1

You're probably overwhelming the actual calculation time with the output time, and running into a fluke of the buffering. A profiler would show you what's actually consuming the time.

Answer 2

The Math.sqrt method defers to StrictMath.sqrt, which is done in hardware or native code. (Look at the source for the JDK - you'll see that it's a native method.) This is certainly faster than anything you'll write. It might even be using the same algorithm that you coded. It's well known. Your method is simply Newton's method for calculating square roots. It's been known since Babylon; Newton simply rederived it using calculus. Quadratic convergence is good.

Whatever you've done, it's unlikely that you've discovered anything new or noteworthy. Sounds like something having to do with IO is artificially biasing the results.

Answer 3

Kudos for trying to improve on an existing implementation; even if you fail, you can learn a lot about algorithms in the process. Naturally, you have to test your alternative using this kind of micro-benchmark. Unfortunately, there are numerous pitfalls. In particular, don't mix irrelevant code, e.g testing and output, with your calculation; do warm up the JVM early in your test. There's more in this article on bechmarking. Also, when comparing floating point values, consider these Guidelines for comparing floating point numbers.

Answer 4

I could not reproduce your results. Tried some times using Eclipse Galileo and JDK 1.6.0.

For 80000, output disabled, I got something like:

Math: 15 milliseconds
I:    32 milliseconds

small times, It would be better to use System.nanoTime() or more interactions.

For 80000, output enabled:

Math: 3609 milliseconds
I:    4906 milliseconds

So probably the problem is the way that output is handled (scrolling, buffering, ...)