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

Groups > comp.lang.c > #59316

Re: Test for overflow

Cross-posted to 2 groups.

Show all headers | View raw

On 03/30/2015 01:20 PM, James Kuyper wrote:
...
> 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.

All occurrences of x%base above should have been
x*base/(ULLONG_MAX+1), where the left and right operands of '/' are
evaluated mathematically without overflow, but where the division
results in an integer value rounded towards zero, per C rules. My
description should make slightly more sense that way :-}. I can't quite
figure out the train of thought that led me to use the simpler
expression, but it had something to do with the fact that the range of
values is the same for both expressions.

The correct expression has precisely the behavior I intended - I just
gave the wrong expression.

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