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

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) ;
  } ;

[download]
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)) ;
  } ;

[download]
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.

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

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

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

    [download]

    works is because the max is really 

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

    [download]
[reply]
[d/l]
[select]

      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 ?

[reply]
[d/l]
[select]

        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]

In Section Seekers of Perl Wisdom