Detecting ineger overflow

[TheHobbit]

Reverend monks,

Please enlighten me.... I'd like to detect overflow during integer operations. Using the integer pragma guarantees that Perl does not converts integers to reals, but it doesn't detect overflow...

I'm trying to write a Perl module to do arithmetic on arbitrary precision integers. Obviously, these new operation will pay an overload on built-in operators for these cases in which the latter can be used. So I'd like to use standard built-in whenever possible. I tried to do something like

sub add {
  use integers;
  my $result = eval {$_[0] + $_[1]};
  return $result if (defined $result);
  goto &myadd;
}

where myadd is the subroutine handling the case where one at least is a "big" integer.. Well, it didn't work :( Even with the inter pragma, overflow errors aren't detected... Any idea?

TheHobbit</strong/

[dchetlin]

If you'll only be adding positive numbers and you can guarantee that all parameters passed to add() will be within integer range, a heuristic as simple as this will work:

sub add {
    use integer;
    my $result = $_[0] + $_[1];
    return $result if $result < $_[0] or $result < $_[1];
    goto &myadd;
}

That technique can be extended if you need to handle negative overflow as well.

If you can't guarantee the integrity of your parameters, you'll need to know in advance the overflow point of the system you're on. This is something that you could potentially test for in your Makefile.PL. Once you know that, you can test each incoming parameter against the top and bottom, and then add them if they pass.

P.S. A few points about quidity's response above: I believe that due to the nature of arbitrary precision integer math, making these checks beforehand will be a speed win in most cases. Also, Math::BigInt is disgustingly slow; if you want to be embarassed, compare it to Python or Ruby's built-in bigints for speed. There is a Math::BigIntFast on the CPAN -- I haven't benchmarked it yet. You might take a look at that.

Another plus for Python and Ruby is that they automatically upgrade to bigints/bignums, while you have to explicitly load the BigInt library and do it by hand in Perl. This is something I'd very much like to see.

P.P.S. Nick Clark is working on some modifications that will make integer math in Perl be much more sensible (though I haven't yet heard any plans to involve bigints). If you're interested in this sort of thing, take a look here, for instance.

-dlc

[tye]

Math::BigInt was an experiment and shouldn't have gotten such a nice name. I think Bit::Vector does much the same things and more much more quickly.

        - tye (but my friends call me "Tye")

[quidity]

You should be able to work out if you are going to get an overflow by comparing the result with the largest possible integer value for your system. Then you can fall through to using BigInt's.

You would be clearer by using Math::BigInt thoughout for all integer values. This allows you to use integers of arbitary size (given certain memory requirements, of course). Math::BigInt . It allows you to overload all mathematical operators when integers are declared using the format below:

use Math::BigInt;
$i = new Math::BigInt '123 456 789 123 456 789';

[tilly]

Have you benchmarked it?

Math::BigInt is abysmal on performance. Something about on every operation parsing a string into an array of integers, doing your operation, then coercing that back into a string...

Try it if you don't believe me.

[tye]

C ignores integer overflow so Perl does as well.

I suggest you drop the use integer (no "s") and check for "mantissa overflow" with:

sub add {
    my $result= $_[0] + $_[1];
    if(  1+$result == $result  )  goto &myadd;
    return $result;
}

then you can do deal with 56-bit integers the way Perl normally deals with 56-bit integers and roll your own when you need more bits than that. I haven't done much analysis on my suggestion so there may be corner cases where this won't work very well. ):
        - tye (but my friends call me "Tye")