Re^2: Largest integer in 64-bit perl

[ikegami]

How would you use a binary search to find the first gap?

[LanX]

I would try to test the OP's problem that predecessor or successor are identical in numerical comparison.

use v5.12;
use warnings;

#say "Mode: ", my $mode = $ARGV[0] // 0;

use Config; say $Config{ivsize}; say $Config{nvsize};

sub test {
  my ($mode) = @_;
  say "**** Mode: $mode";
  my $now=1;
  for my $x ( 1.. 65) {
    $now =
      $mode == 0 ? 2 * $now    :
      $mode == 1 ? 2 ** $x     :
      $mode == 2 ? 2 ** $x  -1 :
      die "Mode=$mode not implemented yet";

    if ( $now == $now-1 or $now == $now+1 ) {
      print "Problem at $now = 2**$x\n";
      printf "%22u %22u %22u\n",$now-1,$now,$now+1;
      last;
    }
  }
}

test($_) for 0..2;

this will break at 2**64 when I stay purely integer

NB: I didn't implement the full binary search, since there is no backtracking yet

But I'm getting weird conversion results when leaving the realm of integer (see the "modes"), these are most likely side-effects of starting with a float (or bugs). Probably better to use Hex-strings.

perl /home/lanx/perl/pm/integer-gap.pl
8
8
**** Mode: 0
Problem at 1.84467440737096e+19 = 2**64
  18446744073709551615   18446744073709551615   18446744073709551615
**** Mode: 1
Problem at 9.00719925474099e+15 = 2**53
      9007199254740991       9007199254740992       9007199254740993
**** Mode: 2
Problem at 4.61168601842739e+18 = 2**62
   4611686018427387904    4611686018427387904    4611686018427387904

YMMV...

Update

In hindsight, the cleanest approach would be to only rely on addition and substraction of integers. No multiplications or exponentions (which might be implemented as approximation)

Since the last safe interval is guaranteed to be an integer too.

[syphilis]

I would try to test the OP's problem that predecessor or successor are identical in numerical comparison.

I haven't looked too closely, but I suspect that the fact that the power operator (**) always returns an NV might be causing problems.
You might be better off using the << operator:

D:\>perl -MDevel::Peek -we "Dump (2**62); Dump ((2**62) + 1); Dump ((2
+**62) - 1);"
SV = NV(0x1d26f8d3f20) at 0x1d26f8d3f38
  REFCNT = 1
  FLAGS = (PADTMP,NOK,READONLY,PROTECT,pNOK)
  NV = 4.6116860184273879e+18
SV = NV(0x1d26f8dbb88) at 0x1d26f8dbba0
  REFCNT = 1
  FLAGS = (PADTMP,NOK,READONLY,PROTECT,pNOK)
  NV = 4.6116860184273879e+18
SV = NV(0x1d26f8d4ac0) at 0x1d26f8d4ad8
  REFCNT = 1
  FLAGS = (PADTMP,NOK,READONLY,PROTECT,pNOK)
  NV = 4.6116860184273879e+18

D:\>perl -MDevel::Peek -we "Dump (1<<62); Dump ((1<<62) + 1); Dump ((1
+<<62) - 1);"
SV = IV(0x132ea044988) at 0x132ea044998
  REFCNT = 1
  FLAGS = (PADTMP,IOK,READONLY,PROTECT,pIOK)
  IV = 4611686018427387904
SV = IV(0x132ea0449e8) at 0x132ea0449f8
  REFCNT = 1
  FLAGS = (PADTMP,IOK,READONLY,PROTECT,pIOK)
  IV = 4611686018427387905
SV = IV(0x132ea0442c8) at 0x132ea0442d8
  REFCNT = 1
  FLAGS = (PADTMP,IOK,READONLY,PROTECT,pIOK)
  IV = 4611686018427387903

The first one-liner results in 3 identical values; the second one-liner results in 3 different values.
It's all just part of the fun we have when we use the utterly insane perl configuration where IV precision is greater than NV precision ;-)

Cheers,
Rob

[LanX]

> the power operator (**) always returns an NV

sure that's why I said we must stay in the "realm of integers" for a proper binary search.

I'm not sure about the "always" tho

> You might be better off using the << operator:

That's the classic approach, but I would choose a "pure" algorithm using + only, to find the point where adding two integers creates a non-integer.