Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #59292

Re: Test for overflow

Cross-posted to 2 groups.

Show all headers | View raw

On 03/30/2015 07:17 AM, jacob navia wrote:
> Hi the math experts!
> 
> When parsing a digit sequence I test for overflow not by calculating the 
> maximum number of digits allowed but just with the test
> 
> tvalue = value * base;
> 
> if (tvalue < value) {
>     // overflow detected
> }
> 
> I am assuming then that
> 
> if value * base > 2^64 then
>     value * base mod 2^64 < value
> 
> for base >= 2 and base <= 36.
> 
> Is this correct?

I hope you're also assuming that value*base is computed using an
unsigned type - if not:

"If an exceptional condition occurs during the evaluation of an
expression (that is, if the result is not mathematically defined or not
in the range of representable values for its type), the behavior is
undefined." (6.5p5)
This clause isn't there just for the pleasure of pedants like myself -
it's present because there have been (and probably still are)
implementations where the behavior of such code would probably surprise you.

> I do not have the proof of it. Maybe one of the math people can help me out?


Even for unsigned types, tvalue < value is not guaranteed for base > 2.

Consider a plot of y=x*base as a C expression in unsigned long long,
(which therefore obeys modular arithmetic) as a function of x. It
consists of parallel lines, each with a slope equal to the base. Each of
those lines starts near y==0, and ends near y==ULLONG_MAX, and can be
labelled with the value of x/base, which ranged from 0 to base-1. The
total number of such linesfor 0 <= x && x <= ULLONG_MAX equals 'base'.

Compare that plot with a plot of y=x. The line for x%base==0 starts at
x=0, y=0, but then stays entire above y=x. The line for x%base ==
(base-1) stays entirely below y=x unless ULLONG_MAX%base == 0, in which
case they meet at x=ULLONG_MAX, y=ULONG_MAX. So for base==2, your test
works perfectly.
However, for every line where 0 < x%base && x%base < base - 1 crosses
y=x. Therefore, your test will misclassify some of the values of tvalue
in that range. It will also mishandle ULLONG_MAX*base if ULLONG_MAX%base==0.

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Test for overflow jacob navia <jacob@jacob.remcomp.fr> - 2015-03-30 13:17 +0200
  Re: Test for overflow Lőrinczy Zsigmond <zsiga@nospam.for.me> - 2015-03-30 13:34 +0200
  Re: Test for overflow Richard Damon <Richard@Damon-Family.org> - 2015-03-30 07:42 -0400
    Re: Test for overflow asetofsymbols@gmail.com - 2015-03-30 04:47 -0700
      Re: Test for overflow jacob navia <jacob@jacob.remcomp.fr> - 2015-03-30 13:57 +0200
        Re: Test for overflow Richard Damon <Richard@Damon-Family.org> - 2015-03-30 08:24 -0400
  Re: Test for overflow Richard Heathfield <rjh@cpax.org.uk> - 2015-03-30 13:03 +0100
  Re: Test for overflow Tim Rentsch <txr@alumni.caltech.edu> - 2015-03-30 06:54 -0700
  Re: Test for overflow James Kuyper <jameskuyper@verizon.net> - 2015-03-30 13:20 -0400
    Re: Test for overflow James Kuyper <jameskuyper@verizon.net> - 2015-03-30 13:32 -0400
    Re: Test for overflow James Kuyper <jameskuyper@verizon.net> - 2015-03-30 19:43 -0400
      Re: Test for overflow jacob navia <jacob@jacob.remcomp.fr> - 2015-03-31 07:11 +0200
        Re: Test for overflow James Kuyper <jameskuyper@verizon.net> - 2015-03-31 13:41 -0400
          Re: Test for overflow jacob navia <jacob@jacob.remcomp.fr> - 2015-03-31 19:48 +0200
            Re: Test for overflow James Kuyper <jameskuyper@verizon.net> - 2015-03-31 13:58 -0400
  Re: Test for overflow Thomas Jahns <jahns@idontlikespam.dkrz.de> - 2015-04-01 10:12 +0200
    Re: Test for overflow Richard Heathfield <rjh@cpax.org.uk> - 2015-04-01 09:43 +0100
      Re: Test for overflow Thomas Jahns <jahns@idontlikespam.dkrz.de> - 2015-04-01 10:59 +0200
        Re: Test for overflow Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-04-01 04:07 -0700
          Re: Test for overflow raltbos@xs4all.nl (Richard Bos) - 2015-04-01 13:52 +0000

csiph-web