Can we assume that x == (int)sqrt(x * x) for all positive integers?

user_12278291 0
Viewed 431

In C++ the sqrt function operates only with double values.

If we use integers (unsigned long long) can we be sure that

x == sqrt(x * x)

for any positive x where x * x <= MAXIMUM_VALUE?

Is it depend on the machine architecture and compiler?

math c c++ java
5 Answers

In Java, Math.sqrt(x) takes a double value. You stated that x is such that x * x is below Integer.MAX_VALUE. Every integer is perfectly representable in double - double in java is explicitly defined as an iEEE-754 style double with a 52-bit mantissa; therefore in java a double can perfectly represent all integral values between -2^52 and +2^52, which easily covers all int values (as that is defined as signed 32-bit on java), but it does not cover all long values. (Defined as signed 64-bit; 64 is more than 52, so no go).

Thus, x * x loses no precision when it ends up getting converted from int to double. Then, Math.sqrt() on this number will give a result that is also perfectly representable as a double (because it is x, and given that x*x fits in an int, x must also fit), and thus, yes, this will always work out for all x.

But, hey, why not give it a shot, right?

public static void main(String[] args) {
    int i = 1;
    while (true) {
        if (i * i < 0) break;
        int j = (int) Math.sqrt(i * i);
        if (i != j) System.out.println("Oh dear! " + i + " -> " + j);

        i++;
    }
    System.out.println("Done at " + i);
}

> Done at 46341

Thus proving it by exhaustively trying it all.

Turns out, none exist - any long value such that x * x still fits (thus, is <2^63-1) has the property that x == (long) Math.sqrt(x * x);. This is presumably because at x*x, the number fits perfectly in a long, even if not all integer numbers that are this large do. Proof:

long p = 2000000000L;
for (; true; p++) {
    long pp = p * p;
    if (pp < 0) break;
    long q = (long) Math.sqrt(pp);
    if (q != p) System.out.println("PROBLEM: " + p + " -> " + q);
}
System.out.println("Abort: " + p);

> Abort: 3037000500

Surely if any number exists that doesn't hold, there is at least one in this high end range. Starting from 0 takes very long.

But do we know that sqrt will always return an exact value for a perfect square, or might it be slightly inaccurate?

We should - it's java. Unlike C, almost everything is 'well defined', and a JVM cannot legally call itself one if it fails to produce the exact answer as specified. The leeway that the Math.sqrt docs provide is not sufficient for any answer other than precisely x to be a legal implementation, therefore, yes, this is a guarantee.

In theory the JVM has some very minor leeway with floating point numbers, which strictfp disables, but [A] that's more about using 80-bit registers to represent numbers instead of 64, which cannot possibly ruin this hypothesis, and [B] a while back a java tag question showed up to show strictfp having any effect on any hardware and any VM version and the only viable result was a non-reproducible thing from 15 years ago. I feel quite confident to state that this will always hold, regardless of hardware or VM version.

user_7686440

Just try it. Yes it works in Java, for non-negative numbers. Even works for long contrary to common opinion.

class Code {
    public static void main(String[] args) throws Throwable {
        for (long x=(long)Math.sqrt(Long.MAX_VALUE);; --x) {
            if (!(x == (long)Math.sqrt(x * x))) {
                System.err.println("Not true for: "+x);
                break;
            }
        }
        System.err.println("Done");
    }
}

(The first number that doesn't work is 3037000500L which goes negative when squared.)

Even for longs, the range of testable values is around 2^31 or 2*10^9 so for something this trivial it is reasonable to check every single value. You can even brute force reasonable cryptographic functions for 32-bit values - something more people should realise. Won't work so well for the full 64 bits.

Tom_Hawtin_-_tackline_47250

I think we can believe.

Type casting a floating point number to an integer is to take only integer part of it. I believe you may concern, for example, sqrt(4) yields a floating point number like 1.999...9 and it is type casted to 1. (Yielding 2.000...1 is fine because it will be type casted to 2.)

But the floating number 4 is like

(1 * 2-0 + 0 + 2-1 + ... + 0 * 2-23) * 22

according to Floating-point arithmetic.

Which means, it must not be smaller than 4 like 3.999...9. So also, sqrt of the number must not be smaller than

(1 * 2-0) * 2

So sqrt of a square of an integer will at least yield a floating point number greater than but close enough to the integer.

user_42271750

BigInteger - sqrt(since 9)

  1. Use cases requiring tighter constraint over possibilities of overflow can use BigInteger
  2. BigInteger should work for any practical use case.
  3. Still for normal use case, this might not be efficient.

Constraints

BigInteger Limits

BigInteger must support values in the range -2^Integer.MAX_VALUE (exclusive) to +2^Integer.MAX_VALUE (exclusive) and may support values outside of that range. An ArithmeticException is thrown when a BigInteger constructor or method would generate a value outside of the supported range. The range of probable prime values is limited and may be less than the full supported positive range of BigInteger. The range must be at least 1 to 2500000000.
Implementation Note:

In the reference implementation, BigInteger constructors and operations throw ArithmeticException when the result is out of the supported range of -2^Integer.MAX_VALUE (exclusive) to +2^Integer.MAX_VALUE (exclusive).

Array size limit when initialized as byte array

String length limit when initialized as String

Definitely may not support 1/0

jshell> new BigInteger("1").divide(new BigInteger("0"))
|  Exception java.lang.ArithmeticException: BigInteger divide by zero
|        at MutableBigInteger.divideKnuth (MutableBigInteger.java:1178)
|        at BigInteger.divideKnuth (BigInteger.java:2300)
|        at BigInteger.divide (BigInteger.java:2281)
|        at (#1:1)

An example code

import java.math.BigInteger;
import java.util.Arrays;
import java.util.List;

public class SquareAndSqrt {

    static void valid() {
        List<String> values = Arrays.asList("1", "9223372036854775807",
            "92233720368547758079223372036854775807", 
            new BigInteger("2").pow(Short.MAX_VALUE - 1).toString());

        for (String input : values) {
            final BigInteger value = new BigInteger(input);
            final BigInteger square = value.multiply(value);
            final BigInteger sqrt = square.sqrt();

            System.out.println("value: " + input + System.lineSeparator()
                + ", square: " + square + System.lineSeparator()
                + ", sqrt: " + sqrt + System.lineSeparator()
                + ", " + value.equals(sqrt));

            System.out.println(System.lineSeparator().repeat(2)); // pre java 11 - System.out.println(new String(new char[2]).replace("\0", System.lineSeparator()));
        }
    }

    static void mayBeInValid() {
        try {
            new BigInteger("2").pow(Integer.MAX_VALUE);
        } catch (ArithmeticException e) {
            System.out.print("value: 2^Integer.MAX_VALUE, Exception: " + e);
            System.out.println(System.lineSeparator().repeat(2));
        }
    }

    public static void main(String[] args) {
        valid();
        mayBeInValid();
    }
}
user_151024590
user_140907470
Related