in reply to Re^6: 64-bit digest algorithms
in thread 64-bit digest algorithms

I think that rather depends on what 'max' one is looking for. In this case the 'max' in question is the largest 2^(n-1) - 1 that can be exactly represented in floating form (IEEE 754 64-bit binary). This value corresponds to the maximum (positive) value of an n bit +ve 2's complement integer -- which was the object of interest.

Update: in the interests of clarity, the striken stuff in the next two paragraphs may be ignored, and in the second of the two, the underlined stuff replaces the striken stuff.

The reason this works is because when i = 54 the normalised intermediate result of the floating point sum (2^54) - 1 is 54 '1's, thus: 1.111...111:1 where the '.' is the binary point, the 111...111 is the 52 bit fraction, and the :1 is the rounding bit. This is then rounded to even. (I'll gloss over how and why this is round to even and not round up.)

Whereas, when i = 53 for (2^53) - 1 the intermediate result is 53 '1's, so no rounding, and there is an all '1's mantissa, which is what one was looking for.

The point was to show that a useful subset of the values representable in floating point form contains all the values of a signed (2's complement) integer of at most 54 bits.

I was not trying to show how many other integer values can be exactly represented as floating point values. One of those is +2^53, which just happens to be right next to the maximum 54-bit signed (2's and 1's complement) integer value. So what ?

Replies are listed 'Best First'.
Re^8: 64-bit digest algorithms
by ikegami (Patriarch) on Nov 17, 2008 at 02:37 UTC

    I think that rather depends on what 'max' one is looking for.

    We were talking about the size of the largest range of integers that can accurately be represented by double-precision floats. That's given by floor(log2($upper-$lower+1)). And in this case, the upper bound of that range is 2**53. If the range was -1000..64535, then answer would be 16, not 9 or 15.

    This is then rounded to even.

    I didn't follow what you said in that paragraph, but there's no rounding involved in storing 2**53 in a float. It's stored precisely (Sign = 0, Exponent = 53, Mantissa = 0).

[reply]
      We were talking about the size of the largest range of integers that can accurately be represented by double-precision floats.

      Ah. I see where the confusion arises. However, what I was addressing was how that can be expressed in terms of an n-bit signed integer, saying:

      So, for practical purposes a 64-bit IEEE-754 double precision floating point value can act as a 54-bit signed integer (with the usual 2's complement -ve values).

      The range of integers that can be represented is, of course, -(2^53)..+(2^53) (inclusive) -- in the sense that there are no gaps between the integers in that range. Outside that range there are gaps, for example ((2^53)+2) exists, but ((2^53)+1) does not. (Lurking inside that range is -0, but we're glossing over that.)

      However, we're pretty familiar with the properties of an n-bit signed integer. In those terms, we have a 54-bit signed integer, noting the limitations of this, including:

      • it misses out the "extra" +(2^53) value.

      • it is strictly a signed integer -- there is no 54-bit unsigned integer.

      • while it's unlikely you'll ever see one, there is -0.

      • all arithmetic is floating point (!), so don't expect, for example, signed integer overflow or underflow behaviour !

      I think those are the important caveats. (Noting that these days "signed" is implicitly "two's complement".)

      I didn't follow what you said in that paragraph, but there's no rounding involved in storing 2**53 in a float.

      I couldn't see where I'd talked about storing 2^53 in a float. However, I've updated the posting and hope that has reduced any scope for confusion. If it's still not clear, I'll be happy to keep improving it :-)

      (Off topic).

      It's reaching back a fair way... the old CDC's used one's complement integers and one's complement reals ! But I doubt any of those are still running.

      Does anyone know of a not two's complement machine actual use these days ?

      Or, for that matter, not IEEE-754 floating point ?

      The C99 standard has a good definition of "Integer types". I have the ISO/IEC 9899:1999 (E) in front of me. I imagine that this refects most people's understanding of integers.

      It specifies that the representation of a signed integer comprises a number of "value bits" and a "sign bit". (Leaving aside the optional "padding bits".)

      It specifies that the value part represents values in the range 0..((2^M)-1), where M is the number of value bits. This is the value of the integer when the sign bit is zero.

      It specifies the value of the integer when the sign bit is one, allowing for sign and magnitude, two's complement and one's complement implementations of negative integers.

      The precision is defined to be the number of value bits. The width is defined to be the number of value and sign bits (so is one greater than the precision, for signed integers).

      In these terms, the "integer range" of IEEE-754 double floating point format approximates most closely to a sign and magnitude signed integer with 53-bit precision -- but that leaves out -(2^53) as well as +(2^53) !

[reply]
[d/l]

In Section Seekers of Perl Wisdom