XPost: comp.lang.c   
   From: jameskuyper@verizon.net   
      
   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.   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)