third_party/lcov/example/methods/gauss.c

   1 /*
   2  *  methods/gauss.c
   3  *
   4  *  Calculate the sum of a given range of integer numbers.
   5  *
   6  *  Somewhat of a more subtle way of calculation - and it even has a story
   7  *  behind it:
   8  *
   9  *  Supposedly during math classes in elementary school, the teacher of
  10  *  young mathematician Gauss gave the class an assignment to calculate the
  11  *  sum of all natural numbers between 1 and 100, hoping that this task would
  12  *  keep the kids occupied for some time. The story goes that Gauss had the
  13  *  result ready after only a few minutes. What he had written on his black
  14  *  board was something like this:
  15  *
  16  *    1 + 100 = 101
  17  *    2 + 99  = 101
  18  *    3 + 98  = 101
  19  *    .
  20  *    .
  21  *    100 + 1 = 101
  22  *
  23  *    s = (1/2) * 100 * 101 = 5050
  24  *
  25  *  A more general form of this formula would be
  26  *
  27  *    s = (1/2) * (max + min) * (max - min + 1)
  28  *
  29  *  which is used in the piece of code below to implement the requested
  30  *  function in constant time, i.e. without dependencies on the size of the
  31  *  input parameters.
  32  *
  33  */
  34
  35 #include "gauss.h"
  36
  37
  38 int gauss_get_sum (int min, int max)
  39 {
  40         /* This algorithm doesn't work well with invalid range specifications
  41            so we're intercepting them here. */
  42         if (max < min)
  43         {
  44                 return 0;
  45         }
  46
  47         return (int) ((max + min) * (double) (max - min + 1) / 2);
  48 }