OLD | NEW |
| (Empty) |
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 } | |
OLD | NEW |