mood.c: Avoid overflow in update_quadratic_deviation().
authorAndre Noll <maan@tuebingen.mpg.de>
Wed, 16 Mar 2016 21:48:54 +0000 (22:48 +0100)
committerAndre Noll <maan@tuebingen.mpg.de>
Mon, 28 Mar 2016 17:15:55 +0000 (17:15 +0000)
The last multiplication of the expression returned can overflow. This
patch replaces the expression by an equivalent one which avoids to
multiply large numbers.

mood.c

diff --git a/mood.c b/mood.c
index 415e170..45b051a 100644 (file)
--- a/mood.c
+++ b/mood.c
@@ -652,7 +652,8 @@ static int add_if_admissible(struct osl_row *aft_row, void *data)
  * the last number a_n was replaced by b) may be computed in O(1) time in terms
  * of n, q, a_n, b, and S as
  *
- *     q' = q + d * s - (2 * S + d) * d / n,
+ *     q' = q + d * s - (2 * S + d) * d / n
+ *        = q + d * (s - 2 * S / n - d /n),
  *
  * where d = b - a_n, and s = b + a_n.
  *
@@ -669,7 +670,7 @@ _static_inline_ int64_t update_quadratic_deviation(int64_t n, int64_t old_qd,
 {
        int64_t delta = new_val - old_val;
        int64_t sigma = new_val + old_val;
-       return old_qd + delta * sigma - (2 * old_sum + delta) * delta / n;
+       return old_qd + delta * (sigma - 2 * old_sum / n - delta / n);
 }
 
 static int update_afs_statistics(struct afs_info *old_afsi, struct afs_info *new_afsi)