Overview

In a programming contest, I summarized the pitfalls I was addicted to and how to avoid them, as well as my own reflection on the error in Java's Math.sqrt method.

Target

java version: 1.8

I think that the behavior is almost the same in other versions, more specifically in other languages, but I have confirmed the operation with this version, so just in case.

Introduction

The sqrt method of Java's Math class is a method that can find the square root of a numerical value given in double type, and is often used when performing numerical calculations.

However, of course, there are some errors in the results.

In many cases, the result is negligible, but in some cases the error is non-negligible.

In this article, I'll show you some of the cases I've encountered and give examples of how to avoid them.

Cases where error became a problem

In a programming contest I participated in, I needed to write the following code.

$ a \ leq 10 ^ {18} $ When given a positive integer $ a $, we want to find the maximum value of $ b $ that satisfies $ b ^ {2} <a $.

Sample code 1

Here is the code I wrote first. (Added on April 9, 2018) As you pointed out in the comments, this code is a little wasteful. "Sample code corrected version" has been added at the end.

`sample1.java(Excerpt)`


    private static long floorSqrt (long a) {
        long b = (long)Math.sqrt(a);
        if (b*b == a) {
            return b-1;
        } else {
            return b;
        }
    }

I will explain briefly.

If $ a $ is a square number (a number equal to the square of a natural number),
-> The $ b $ to be calculated is $ \ sqrt {a} $ (= integer value) minus 1.
If $ a $ is not a square number,
-> The $ b $ you want is the number of $ \ sqrt {a} $ (= non-integer value) rounded down to the nearest whole number.

At first glance it seems to work, but the above code doesn't work.

Result of sample code 1

(Added on April 9, 2018) As you pointed out in the comments, this code is a little wasteful. "Sample code corrected version" has been added at the end.

`sample1.java`


public class Sample1 {
    public static void main(String[] args) {
        System.out.println("lessThanSqrt (99)=" + lessThanSqrt (99));
        System.out.println("lessThanSqrt (100)=" + lessThanSqrt (100));
        System.out.println("lessThanSqrt (999999999)=" + lessThanSqrt (9999999999L));
        System.out.println("lessThanSqrt (10000000000)=" + lessThanSqrt (10000000000L));
        System.out.println("lessThanSqrt (999999999999999999)="+lessThanSqrt (999999999999999999L));
        System.out.println("lessThanSqrt (1000000000000000000)=" + lessThanSqrt  (1000000000000000000L));

    }
    private static long lessThanSqrt (long a) {
        long b = (long)Math.sqrt(a);
        if (b*b == a) {
            return b-1;
        } else {
            return b;
        }
    }

The execution result of the above sample code is as follows.

lessThanSqrt (99)=9
lessThanSqrt  (100)=9
lessThanSqrt (999999999)=99999
lessThanSqrt  (10000000000)=99999
lessThanSqrt (999999999999999999)=1000000000
lessThanSqrt (1000000000000000000)=999999999

If the value is extremely high, the result is strange.

Problems with sample code 1

The cause of this can be understood by looking at the execution result of the sample code below.

`sample1_1.java`


public class Sample1_1 {
    public static void main(String[] args) {
        System.out.println(Math.sqrt(99999999999999L));
        System.out.println(Math.sqrt(100000000000000L));
        System.out.println(Math.sqrt(9999999999999999L));
        System.out.println(Math.sqrt(10000000000000000L));
        System.out.println(Math.sqrt(999999999999999999L));
        System.out.println(Math.sqrt(1000000000000000000L));
    }
}

Execution result

9999999.99999995
1.0E7
1.0E8
1.0E8
1.0E9
1.0E9

Looking at the above results, if $ n> 8 $, the results of $ \ sqrt {10 ^ {2n}} $ and $ \ sqrt {10 ^ {2n} -1} $ are the same. I am.

This is a double type precision issue.

As for the precision of the double type, since only about 15 digits of information can be retained, it is not possible to retain information with a larger number of digits, resulting in an error from the original value.

In most cases, the effect is small, but if the number has 9 decimal places, the error may change the number in the integer part.

The square root calculation for large numbers is prone to the above situations.

Sample code 2

Below is the code that takes into account the problem of sample code 1 and adds the logic to correct the error. (Added on April 9, 2018) As you pointed out in the comments, this code is a little wasteful. "Sample code corrected version" has been added at the end.

`sample2.java`


public class Sample2 {

    public static void main(String[] args) {
        System.out.println("lessThanSqrt (99)=" + lessThanSqrt (99));
        System.out.println("lessThanSqrt (100)=" + lessThanSqrt (100));
        System.out.println("lessThanSqrt (999999999)=" + lessThanSqrt (9999999999L));
        System.out.println("lessThanSqrt (10000000000)=" + lessThanSqrt (10000000000L));
        System.out.println("lessThanSqrt (999999999999999999)="+lessThanSqrt (999999999999999999L));
        System.out.println("lessThanSqrt (1000000000000000000)=" + lessThanSqrt (1000000000000000000L));

    }
    
    private static long lessThanSqrt (long a) {
        long b = longSqrt(a);
        if (b*b == a) {
            return b-1;
        } else {
            return b;
        }
    }
    
    private static long longSqrt (long a) {
        long b = (long)Math.sqrt(a);
        //If the obtained value is squared and exceeds the original value
        //Because the error is 1 larger
        //Returns the value minus 1 to correct the error
        if(b*b > a) {
            b--;
        }
        return b;
    }
}

Execution result

lessThanSqrt (99)=9
lessThanSqrt (100)=9
lessThanSqrt (999999999)=99999
lessThanSqrt (10000000000)=99999
lessThanSqrt (999999999999999999)=999999999
lessThanSqrt (1000000000000000000)=999999999

You can now get the correct results.

Summary

When using sqrt for problems dealing with integers, be aware of the above errors.

Supplementary notes

Not limited to + sqrt, in general, when performing floating-point type calculations, it is necessary to consider errors. If you don't usually handle floating point types too much, you should be careful because consideration tends to be omitted.

Most of the methods of Math class handle double type, so be careful about errors. It can also be a hotbed of bugs, so for problems that handle only integers, I think it's best to combine only int and long (you don't have to worry about errors, and the processing speed is often faster. Because).
It may be good for studying algorithms to consider whether the methods of the Math class can be implemented using only integers.

(Added on April 9, 2018) Sample code corrected version

Here is a correction of the useless part of the sample code to an efficient code.

`Sample1Modified.java(Excerpt)`


    private static long lessThanSqrt (long a) {
        return (long)Math.sqrt(a-1);
    }

`Sample2Modified.java(Excerpt)`


    private static long lessThanSqrt (long a) {
        return longSqrt(a-1);
    }

It is enough to take $ \ sqrt {a-1} $ without dividing the case.

Java Math.sqrt Error Pit