From 511087311a2eaebf91d2e230ca2f1b28996d9969 Mon Sep 17 00:00:00 2001
From: Han-Wen Nienhuys <hanwen@xs4all.nl>
Date: Sun, 24 Dec 2006 18:55:38 +0100
Subject: [PATCH] quicker gcd, without divisions. Copy & paste from guile.

---
 flower/rational.cc | 63 +++++++++++++++++++++++++++++++++++-----------
 1 file changed, 48 insertions(+), 15 deletions(-)

diff --git a/flower/rational.cc b/flower/rational.cc
index 748a869841..6822703256 100644
--- 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 ()
 {
-- 
2.39.5