3 ms·

The spacing of floating point numbers have any bearing on their values. To be precise: every integer, positive or negative, with magnitude less than 2^53+1, is

The spacing of floating point numbers have any bearing on their values. To be precise: every integer, positive or negative, with magnitude less than 2^53+1, is exactly represented in double-precision. “Extra values in two’s complement” don’t (and couldn’t possibly) effect this at all, since it is a statement about abstract integers and floating-point numbers, neither of which depends on two’s complement representations. In particular, -2^52 has a sign field of 1, an exponent field of 1023+52=1075, and an all-zero significand field. This number is exactly -2^52.

qznc 7y ago
So the correct implementation of fits_long would be this? int fits_long(double value) { double max = (double) (1L << 52) double min = (double) -max; return min <= value && value <= max; } (assuming a 64bit long)
- aidenn0 7y ago
  It depends on the semantics of fits_long. There are values outside of your min/max range that are representable by 64-bit integers, but if you convert them to a double and back, you may get a different value (off by as much as 4096, since, IIRC, the specification allows any rounding strategy).
- mulle_nat 7y ago
  That would allow a double with a fractional part to return true though, which is not the intention. If you do this before the casted comparison, the cast shouldn't produce an undefined value. I think this is a good solution without using the math library and having access to the FP status registers. Otherwise the lrint solution seems better. int fits_long(double value) { double max = (double) (1L << 52) double min = (double) -max; if( min <= value && value <= max) return( (double) (long) value == value); return( 0); }
  - syockit 7y ago
    Why not nix the range check and just rely on the cast? As pointed out by another poster above, there are double values outside the ±2^53 but fits inside long.
    - qznc 7y ago
      The range check filters out the cases where the cast is undefined.
aidenn0 7y ago
I disagree. The value 2^80 can be exactly represented in double-precision as well, but it is also the most precise representation of 2^28 other integers, so it is ambiguous which integer is being represented. [edit] To clarify, the representation you suggest would also be the best possible representation of -2^52-1.
- stephencanon 7y ago
  That's not how floating-point works. The IEEE 754 standard is quite clear that each floating-point datum represents exactly one real number (or infinity or NaN). Floating-point numbers are not intervals. Analogously, `float x = 2.25; int a = x;` assigns the value two to a, but this does not imply that the integer two also represents 2.25. Two is just two.
  - aidenn0 7y ago
    IMO that's a very wrongheaded way to think about floating-point values. As far as IEEE 754 goes, my only praise for it is that it's significantly better than no floating-point standard (which we had before). Integers are inherently different because calculations with integers are naturally discrete, while floating-point calculations are a discrete approximation of the reals, which are not discrete. There are two general purposes for floating-point numbers: scientific computing, where you start with an imprecise value and the precision multiplicatively accumulates (the original use). And as a hardware optimization for calculation of non-integer values (a common use-case today). In neither case does it make sense to treat a floating-point value as a precise number, which matches common advice to not compare floating-point values by equality.
    - szc 7y ago
      I came here to comment that I think the problem is poorly posed and algorithm chosen to implement it is "backwards". But I also see that StehpenCannon has spoken :-); there is going to be very little chance he is wrong when it comes to arguing about floating point! He also notes the following, but not quite so explicitly... The problem is poorly posed because the question is, which mantissas, exponents and sign bits fit into a long. The algorithm is backwards because simple comparisons in integer space cannot compute this; but I think the algorithm should be, int fits_long(double value) { unsigned int trailingZeros = countOfTrailingZeros(mantissaOf(value)); bool fits = (bitsInAMantissa + 2 - trailingZeros + exponentOf(value) < bitsInALong); return fits; } [Notes: if double is always > 0 and going to an unsigned long, the 2 above would be 1. The 2 represents the sign bit in the double. Given that sizeof(double) == sizeof(long) all bits in the two representations are accounted for, so there is no information loss. checking: mantissa = 0 (with a hidden msb of 1) means, trailingZeros = bitsInAMantissa -> fits will be true when the exponent value can be 0..62. So this represents each of the +/- 2^exponent values mantissa = 1 x bitsInAMantissa means, trailingZeros = 0 -> fits will be true when the exponent value can be 0..(bitsInALong-BitsInAMantissa-2). So, +/- (all ones) * 2^exponent value. The representation for going from double to long is not "smooth". ] countOfTrailingZeros() is a favorite of bit twiddlers. "Hackers Delight" or "bithacks" https://graphics.stanford.edu/~seander/bithacks.html https://graphics.stanford.edu/~seander/bithacks.html [edited to improve readability]

qznc 7y ago

So the correct implementation of fits_long would be this? int fits_long(double value) { double max = (double) (1L << 52) double min = (double) -max; return min <= value && value <= max; } (assuming a 64bit long)

aidenn0 7y ago
It depends on the semantics of fits_long. There are values outside of your min/max range that are representable by 64-bit integers, but if you convert them to a double and back, you may get a different value (off by as much as 4096, since, IIRC, the specification allows any rounding strategy).
mulle_nat 7y ago
That would allow a double with a fractional part to return true though, which is not the intention. If you do this before the casted comparison, the cast shouldn't produce an undefined value. I think this is a good solution without using the math library and having access to the FP status registers. Otherwise the lrint solution seems better. int fits_long(double value) { double max = (double) (1L << 52) double min = (double) -max; if( min <= value && value <= max) return( (double) (long) value == value); return( 0); }
- syockit 7y ago
  Why not nix the range check and just rely on the cast? As pointed out by another poster above, there are double values outside the ±2^53 but fits inside long.
  - qznc 7y ago
    The range check filters out the cases where the cast is undefined.

aidenn0 7y ago

I disagree. The value 2^80 can be exactly represented in double-precision as well, but it is also the most precise representation of 2^28 other integers, so it is ambiguous which integer is being represented. [edit] To clarify, the representation you suggest would also be the best possible representation of -2^52-1.

stephencanon 7y ago
That's not how floating-point works. The IEEE 754 standard is quite clear that each floating-point datum represents exactly one real number (or infinity or NaN). Floating-point numbers are not intervals. Analogously, `float x = 2.25; int a = x;` assigns the value two to a, but this does not imply that the integer two also represents 2.25. Two is just two.
- aidenn0 7y ago
  IMO that's a very wrongheaded way to think about floating-point values. As far as IEEE 754 goes, my only praise for it is that it's significantly better than no floating-point standard (which we had before). Integers are inherently different because calculations with integers are naturally discrete, while floating-point calculations are a discrete approximation of the reals, which are not discrete. There are two general purposes for floating-point numbers: scientific computing, where you start with an imprecise value and the precision multiplicatively accumulates (the original use). And as a hardware optimization for calculation of non-integer values (a common use-case today). In neither case does it make sense to treat a floating-point value as a precise number, which matches common advice to not compare floating-point values by equality.
  - szc 7y ago
    I came here to comment that I think the problem is poorly posed and algorithm chosen to implement it is "backwards". But I also see that StehpenCannon has spoken :-); there is going to be very little chance he is wrong when it comes to arguing about floating point! He also notes the following, but not quite so explicitly... The problem is poorly posed because the question is, which mantissas, exponents and sign bits fit into a long. The algorithm is backwards because simple comparisons in integer space cannot compute this; but I think the algorithm should be, int fits_long(double value) { unsigned int trailingZeros = countOfTrailingZeros(mantissaOf(value)); bool fits = (bitsInAMantissa + 2 - trailingZeros + exponentOf(value) < bitsInALong); return fits; } [Notes: if double is always > 0 and going to an unsigned long, the 2 above would be 1. The 2 represents the sign bit in the double. Given that sizeof(double) == sizeof(long) all bits in the two representations are accounted for, so there is no information loss. checking: mantissa = 0 (with a hidden msb of 1) means, trailingZeros = bitsInAMantissa -> fits will be true when the exponent value can be 0..62. So this represents each of the +/- 2^exponent values mantissa = 1 x bitsInAMantissa means, trailingZeros = 0 -> fits will be true when the exponent value can be 0..(bitsInALong-BitsInAMantissa-2). So, +/- (all ones) * 2^exponent value. The representation for going from double to long is not "smooth". ] countOfTrailingZeros() is a favorite of bit twiddlers. "Hackers Delight" or "bithacks" https://graphics.stanford.edu/~seander/bithacks.html https://graphics.stanford.edu/~seander/bithacks.html [edited to improve readability]