quicker gcd, without divisions.

Copy & paste from guile.

diff --git a/flower/rational.cc b/flower/rational.cc
index 748a8698413e2b86a3569a0a25731e2bf70c7067..6822703256a410433e3235c4fa263b389357a08a 100644 (file)
--- a/flower/rational.cc
+++ b/flower/rational.cc
@@ -74,21 +74,6 @@ Rational::Rational (int n)
 }
 
 
-/*
-  We can actually do a little better. See Knuth 4.5.2
- */
-static inline
-int gcd (int a, int b)
-{
-  int t;
-  while ((t = a % b))
-    {
-      a = b;
-      b = t;
-    }
-  return b;
-}
-
 void
 Rational::set_infinite (int s)
 {
@@ -119,6 +104,54 @@ Rational::mod_rat (Rational div) const
   return r;
 }
 
+
+/*
+  copy & paste from scm_gcd (GUILE).
+ */
+static int
+gcd (long u, long v) 
+{
+  long result = 0;
+  if (u == 0)
+    result = v;
+  else if (v == 0)
+    result = u;
+  else
+    {
+      long k = 1;
+      long t;
+      /* Determine a common factor 2^k */
+      while (!(1 & (u | v)))
+       {
+         k <<= 1;
+         u >>= 1;
+         v >>= 1;
+       }
+      /* Now, any factor 2^n can be eliminated */
+      if (u & 1)
+       t = -v;
+      else
+       {
+         t = u;
+       b3:
+         t = t >> 1;
+       }
+      if (!(1 & t))
+       goto b3;
+      if (t > 0)
+       u = t;
+      else
+       v = -t;
+      t = u - v;
+      if (t != 0)
+       goto b3;
+      result = u * k;
+    }
+
+  return result;
+}
+
+
 void
 Rational::normalize ()
 {