[Gnucash-changes] tweak the equality tests to avoid aliasing effects for large-number

Linas Vepstas linas at cvs.gnucash.org
Fri Jun 25 20:18:18 EDT 2004


Log Message:
-----------
tweak the equality tests to avoid aliasing effects for large-number compares.

Modified Files:
--------------
    gnucash/src/engine:
        gnc-numeric.c
        gnc-numeric.h

Revision Data
-------------
Index: gnc-numeric.c
===================================================================
RCS file: /home/cvs/cvsroot/gnucash/src/engine/gnc-numeric.c,v
retrieving revision 1.35
retrieving revision 1.36
diff -Lsrc/engine/gnc-numeric.c -Lsrc/engine/gnc-numeric.c -u -r1.35 -r1.36
--- src/engine/gnc-numeric.c
+++ src/engine/gnc-numeric.c
@@ -1,6 +1,7 @@
 /********************************************************************
  * gnc-numeric.c -- an exact-number library for accounting use      *
  * Copyright (C) 2000 Bill Gribble                                  *
+ * Copyright (C) 2004 Linas Vepstas <linas at linas.org>               *
  *                                                                  *
  * This program is free software; you can redistribute it and/or    *
  * modify it under the terms of the GNU General Public License as   *
@@ -220,6 +221,16 @@
   return out;
 }
 
+/** Return true of two numbers are equal */
+static inline gboolean
+equal128 (gncint128 a, gncint128 b)
+{
+	if (a.lo != b.lo) return 0;
+	if (a.hi != b.hi) return 0;
+	if (a.isneg != b.isneg) return 0;
+	return 1;
+}
+
 #ifdef TEST_128_BIT_MULT
 static void pr (gint64 a, gint64 b)
 {
@@ -293,8 +304,6 @@
 };
 #endif
 
-static gint64 gnc_numeric_lcd(gnc_numeric a, gnc_numeric b);
-
 /* =============================================================== */
 /* This function is small, simple, and used everywhere below, 
  * lets try to inline it.
@@ -321,6 +330,84 @@
 }
 
 /********************************************************************
+ *  gnc_numeric_lcd
+ *  Find the least common multiple of the denominators of 
+ *  a and b
+ *  XXX FIXME this is a stunningly bad, ill-informed algorithm!!
+ ********************************************************************/
+
+static gint64
+gnc_numeric_lcd(gnc_numeric a, gnc_numeric b) 
+{
+  gint64 current_divisor = 2;
+  gint64 max_square;
+  gint64 three_count = 0;
+  gint64 small_denom;
+  gint64 big_denom;
+
+  if(gnc_numeric_check(a) || gnc_numeric_check(b)) {
+    return GNC_ERROR_ARG;
+  }
+  
+  if(b.denom < a.denom) {
+    small_denom = b.denom;
+    big_denom = a.denom;
+  }
+  else {
+    small_denom = a.denom;
+    big_denom = b.denom;
+  }
+
+  /* special case: smaller divides smoothly into larger */
+  if((big_denom % small_denom) == 0) {
+    return big_denom;
+  }
+  
+  max_square = small_denom;
+  
+  /* the LCM algorithm : factor out the union of the prime factors of the
+   * two args and then multiply the remainders together. 
+   *
+   * To do this, we find the successive prime factors of the smaller
+   * denominator and eliminate them from both the smaller and larger
+   * denominator (so we only count factors on a one-on-one basis),
+   * then multiply the original smaller by the remains of the larger.
+   *
+   * I.e. LCM 100,96875 == 2*2*5*5,31*5*5*5*5 = 2*2,31*5*5
+   *      answer: multiply 100 by 31*5*5 == 387500
+   */
+  while(current_divisor * current_divisor <= max_square) {
+    if(((small_denom % current_divisor) == 0) &&
+       ((big_denom % current_divisor) == 0)) {
+      big_denom = big_denom / current_divisor;
+      small_denom = small_denom / current_divisor;
+    }
+    else {
+      if(current_divisor == 2) {
+        current_divisor++;
+      }
+      else if(three_count == 3) { 
+        current_divisor += 4;
+        three_count = 1;
+      }
+      else {
+        current_divisor += 2;
+        three_count++;
+      }
+    }
+    
+    if((current_divisor > small_denom) ||
+       (current_divisor > big_denom)) {
+      break;
+    }
+  }
+  
+  /* max_sqaure is the original small_denom */
+  return max_square * big_denom;
+
+}
+
+/********************************************************************
  *  gnc_numeric_zero_p
  ********************************************************************/
 
@@ -409,8 +496,9 @@
  *  gnc_numeric_eq
  ********************************************************************/
 
-int
-gnc_numeric_eq(gnc_numeric a, gnc_numeric b) {
+gboolean
+gnc_numeric_eq(gnc_numeric a, gnc_numeric b) 
+{
   return ((a.num == b.num) && (a.denom == b.denom));
 }
 
@@ -419,13 +507,25 @@
  *  gnc_numeric_equal
  ********************************************************************/
 
-int
-gnc_numeric_equal(gnc_numeric a, gnc_numeric b) {
-  if(((a.denom > 0) && (b.denom > 0)) ||
-     ((a.denom < 0) && (b.denom < 0))) {    
+gboolean
+gnc_numeric_equal(gnc_numeric a, gnc_numeric b) 
+{
+  if ((a.denom == b.denom) && (a.denom > 0))
+  {
+    return (a.num == b.num);
+  }
+  if ((a.denom > 0) && (b.denom > 0))
+  {
+    gncint128 l = mult128 (a.num, b.denom);
+    gncint128 r = mult128 (b.num, a.denom);
+    return equal128 (l, r);
+  }
+  if ((a.denom < 0) && (b.denom < 0))
+  {    
     return ((a.num * b.denom) == (a.denom * b.num));
   }
-  else {
+  else 
+  {
     return 0;
   }
 }
@@ -496,7 +596,8 @@
     sum.denom = a.denom;
   }
   else {
-    /* ok, convert to the lcd and compute from there... */
+    /* Computing the LCD minimizes likelyhood of overflow */
+    /* XXX although we should check for overflow ... */
     lcd = gnc_numeric_lcd(a,b);
     sum.num   = a.num*(lcd/a.denom) + b.num*(lcd/b.denom);
     sum.denom = lcd;
@@ -955,83 +1056,6 @@
 
 
 /********************************************************************
- *  gnc_numeric_lcd
- *  Find the least common multiple of the denominators of 
- *  a and b
- ********************************************************************/
-
-gint64
-gnc_numeric_lcd(gnc_numeric a, gnc_numeric b) {
-  gint64 current_divisor = 2;
-  gint64 max_square;
-  gint64 three_count = 0;
-  gint64 small_denom;
-  gint64 big_denom;
-
-  if(gnc_numeric_check(a) || gnc_numeric_check(b)) {
-    return GNC_ERROR_ARG;
-  }
-  
-  if(b.denom < a.denom) {
-    small_denom = b.denom;
-    big_denom = a.denom;
-  }
-  else {
-    small_denom = a.denom;
-    big_denom = b.denom;
-  }
-
-  /* special case: smaller divides smoothly into larger */
-  if((big_denom % small_denom) == 0) {
-    return big_denom;
-  }
-  
-  max_square = small_denom;
-  
-  /* the LCM algorithm : factor out the union of the prime factors of the
-   * two args and then multiply the remainders together. 
-   *
-   * To do this, we find the successive prime factors of the smaller
-   * denominator and eliminate them from both the smaller and larger
-   * denominator (so we only count factors on a one-on-one basis),
-   * then multiply the original smaller by the remains of the larger.
-   *
-   * I.e. LCM 100,96875 == 2*2*5*5,31*5*5*5*5 = 2*2,31*5*5
-   *      answer: multiply 100 by 31*5*5 == 387500
-   */
-  while(current_divisor * current_divisor <= max_square) {
-    if(((small_denom % current_divisor) == 0) &&
-       ((big_denom % current_divisor) == 0)) {
-      big_denom = big_denom / current_divisor;
-      small_denom = small_denom / current_divisor;
-    }
-    else {
-      if(current_divisor == 2) {
-        current_divisor++;
-      }
-      else if(three_count == 3) { 
-        current_divisor += 4;
-        three_count = 1;
-      }
-      else {
-        current_divisor += 2;
-        three_count++;
-      }
-    }
-    
-    if((current_divisor > small_denom) ||
-       (current_divisor > big_denom)) {
-      break;
-    }
-  }
-  
-  /* max_sqaure is the original small_denom */
-  return max_square * big_denom;
-
-}
-  
-
-/********************************************************************
  ** reduce a fraction by GCF elimination.  This is NOT done as a
  *  part of the arithmetic API unless GNC_DENOM_REDUCE is specified 
  *  as the output denominator.
Index: gnc-numeric.h
===================================================================
RCS file: /home/cvs/cvsroot/gnucash/src/engine/gnc-numeric.h,v
retrieving revision 1.16
retrieving revision 1.17
diff -Lsrc/engine/gnc-numeric.h -Lsrc/engine/gnc-numeric.h -u -r1.16 -r1.17
--- src/engine/gnc-numeric.h
+++ src/engine/gnc-numeric.h
@@ -152,13 +152,13 @@
 /** Equivalence predicate: Returns TRUE (1) if a and b are exactly the
  * same (same numerator and denominator)
  */ 
-int gnc_numeric_eq(gnc_numeric a, gnc_numeric b);     
+gboolean gnc_numeric_eq(gnc_numeric a, gnc_numeric b);     
 
 /** Equivalence predicate: Returns TRUE (1) if a and b represent
  *  exactly the same number (ratio of numerator to denominator is
  *  exactly equal)
  */ 
-int gnc_numeric_equal(gnc_numeric a, gnc_numeric b);  
+gboolean gnc_numeric_equal(gnc_numeric a, gnc_numeric b);  
 
 /** Equivalence predicate: Returns TRUE (1) if after both are
  * converted to DENOM using method HOW, a and b are


More information about the gnucash-changes mailing list