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

No! Doubles have 64-bits.

Of which:

With the result being that a 64-bit IEEE-754 double precision floating point value can act as a 53-bit signed integer for some purposes.

If you're going to try to be a pedant, rather than contribute something useful--at least be right.

Replies are listed 'Best First'.
Re^5: 64-bit digest algorithms
by gone2015 (Deacon) on Nov 16, 2008 at 15:33 UTC
    can act as a 53-bit signed integer for some purposes.

    To be even more pedantic... :-)

    ...that would be a 53 bit unsigned integer, or a 54-bit sign and magnitude signed integer (using one bit for the sign); equivalent to a 54-bit 1's complement signed integer.

    Since 1's complement machines are as rare as rocking horse fumet, one might worry about the -0x80....0 minimum value. Happily that is quite comfortably accommodated in floating point form.

    The -0 value is generally treated as zero, so that shouldn't intrude.

    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).

    So:

    for my $n (53..55) { my $max = 2**($n-1) - 1 ; my $min = -(2**($n-1)) ; printf "%4d: -%s..%s\n", $n, show($min), show($max) ; } ; sub show { my ($x) = @_ ; my $ms = int(abs($x)/2**32) ; my $ls = abs($x) - ($ms * 2**32) ; sprintf '0x%04X_%04X_%04X_%04X', ($ms >> 16), ($ms & 0xFFFF), ($ls >> 16), ($ls & 0xFFFF) ; } ;
    gives:
        53: -0x0010_0000_0000_0000..0x000F_FFFF_FFFF_FFFF
        54: -0x0020_0000_0000_0000..0x001F_FFFF_FFFF_FFFF
        55: -0x0040_0000_0000_0000..0x0040_0000_0000_0000
    
    showing that 53-bit (2's complement) signed integer is on the small side, 55-bit is to big, but 54-bits is just right.


    For extra credit, those with 64-bit integers can consider (a) why:

    my $z = 0x0FED_CBA9_8765_4321 ; my $d = 9 ; printf " a = %20s * %d + i, for i = 0..%d\n", "$z", $d, $d ; # 12: 12345678901234567890 : +2345 print " i: a / $d : Error\n" ; foreach my $i (0..$d) { my $a = ($z * $d) + $i ; my $q = $a / $d ; printf " %2d: %20s : %+5d\n", $i, "$q", $q - ($z + int($i/$d)) ; } ;
    gives:
     a =  1147797409030816545 * 9 + i, for i = 0..9
      i:                a / 9 : Error
      0:  1147797409030816545 :    +0
      1: 1.14779740903082e+18 :  +128
      2: 1.14779740903082e+18 :  +128
      3: 1.14779740903082e+18 :  +128
      4: 1.14779740903082e+18 :  +128
      5: 1.14779740903082e+18 :  +128
      6: 1.14779740903082e+18 :  +128
      7: 1.14779740903082e+18 :  +128
      8: 1.14779740903082e+18 :  +128
      9:  1147797409030816546 :    +0
    
    and (b) whether this could be fixed, and finally (c) whether round-to-even is a Good Thing, with particular reference to this case.

    Bug #53784 refers.

      You can't subtract one from something to get the max. The only reason

      my $max = 2**($n-1) - 1 ;

      works is because the max is really

      my $max = 2**($n-1);

        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 ?