Implement gcd in sdk.

runtime/lib/bigint.dart

 // Copyright (c) 2014, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 // Copyright 2009 The Go Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style
 // license that can be found in the LICENSE file.
 
 /*
  * Copyright (c) 2003-2005  Tom Wu
@@ skipping 29 matching lines @@
 
 // A big integer number is represented by a sign, an array of 32-bit unsigned
 // integers in little endian format, and a number of used digits in that array.
 // The code makes sure that an even number of digits is always accessible and
 // meaningful, so that pairs of digits can be processed as 64-bit unsigned
 // numbers on a 64-bit platform. This requires the initialization of a leading
 // zero if the number of used digits is odd.
 class _Bigint extends _IntegerImplementation implements int {
   // Bits per digit.
   static const int _DIGIT_BITS = 32;
+  static const int _LOG2_DIGIT_BITS = 5;
   static const int _DIGIT_BASE = 1 << _DIGIT_BITS;
   static const int _DIGIT_MASK = (1 << _DIGIT_BITS) - 1;
 
   // Bits per half digit.
   static const int _DIGIT2_BITS = _DIGIT_BITS >> 1;
   static const int _DIGIT2_MASK = (1 << _DIGIT2_BITS) - 1;
 
   // Min and max of non bigint values.
   static const int _MIN_INT64 = (-1) << 63;
   static const int _MAX_INT64 = 0x7fffffffffffffff;
@@ skipping 1471 matching lines @@
         if (--i < 0) {
           i = _DIGIT_BITS - 1;
           --j;
         }
       }
     }
     assert(!is1);
     return z._revert(r_digits, r_used)._toValidInt();
   }
 
-  // Returns 1/this % m, with m > 0.
-  int modInverse(int m) {
-    if (m is! int) throw new ArgumentError(m);
-    if (m <= 0) throw new RangeError(m);
-    if (m == 1) return 0;
-    m = m._toBigint();
-    var t = this;
-    if (t._neg || (t._absCompare(m) >= 0)) {
-      t %= m;
-      t = t._toBigint();
+  // If inv is false, returns gcd(x, y).
+  // If inv is true and gcd(x, y) = 1, returns d, so that c*x + d*y = 1.
+  // If inv is true and gcd(x, y) != 1, throws RangeError("Not coprime").
+  static int _binaryGcd(_Bigint x, _Bigint y, bool inv) {
+    var x_digits = x._digits;
+    var y_digits = y._digits;
+    var x_used = x._used;
+    var y_used = y._used;
+    var m_used = x_used > y_used ? x_used : y_used;
+    final m_len = m_used + (m_used & 1);
+    x_digits = _cloneDigits(x_digits, 0, x_used, m_len);
+    y_digits = _cloneDigits(y_digits, 0, y_used, m_len);
+    int s = 0;
+    if (inv) {
+      if ((y_used == 1) && (y_digits[0] == 1)) return 1;
+      if ((y_used == 0) || (y_digits[0].isEven && x_digits[0].isEven)) {
+        throw new RangeError("Not coprime");
+      }
+    } else {
+      if ((x_used == 0) || (y_used == 0)) throw new RangeError(0);
+      if (((x_used == 1) && (x_digits[0] == 1)) ||
+          ((y_used == 1) && (y_digits[0] == 1))) return 1;
+      bool xy_cloned = false;
+      while (x.isEven && y.isEven) {
+        _rsh(x_digits, x_used, 1, x_digits);
+        _rsh(y_digits, y_used, 1, y_digits);
+        s++;
+      }
+      if (s >= _DIGIT_BITS) {
+        var sd = s >> _LOG2_DIGIT_BITS;
+        x_used -= sd;
+        y_used -= sd;
+        m_used -= sd;
+      }
+      if ((y_digits[0] & 1) == 1) {
+        var t_digits = x_digits;
+        var t_used = x_used;
+        x_digits = y_digits;
+        x_used = y_used;
+        y_digits = t_digits;
+        y_used = t_used;
+      }
     }
-    final bool ac = m.isEven;
-    final t_used = t._used;
-    if ((t_used == 1) && (t._digits[0] == 1)) return 1;
-    if ((t_used == 0) || (ac && t.isEven)) throw new RangeError("Not coprime");
-    final m_digits = m._digits;
-    final m_used = m._used;
-    final tuv_len = m_used + (m_used & 1);
-    final t_digits = _cloneDigits(t._digits, 0, t_used, tuv_len);
-    var u_digits = _cloneDigits(m_digits, 0, m_used, tuv_len);
-    var v_digits = _cloneDigits(t_digits, 0, t_used, tuv_len);
+    var u_digits = _cloneDigits(x_digits, 0, x_used, m_len);
+    var v_digits = _cloneDigits(y_digits, 0, y_used, m_len);
+    final bool ac = (x_digits[0] & 1) == 0;
 
     // Variables a, b, c, and d require one more digit.
     final abcd_used = m_used + 1;
     final abcd_len = abcd_used + (abcd_used & 1) + 2;  // +2 to satisfy _absAdd.
     var a_digits, b_digits, c_digits, d_digits;
     bool a_neg, b_neg, c_neg, d_neg;
     if (ac) {
       a_digits = new Uint32List(abcd_len);
       a_neg = false;
       a_digits[0] = 1;
       c_digits = new Uint32List(abcd_len);
       c_neg = false;
     }
     b_digits = new Uint32List(abcd_len);
     b_neg = false;
     d_digits = new Uint32List(abcd_len);
     d_neg = false;
     d_digits[0] = 1;
 
     while (true) {
       while ((u_digits[0] & 1) == 0) {
         _rsh(u_digits, m_used, 1, u_digits);
         if (ac) {
           if (((a_digits[0] & 1) == 1) || ((b_digits[0] & 1) == 1)) {
             if (a_neg) {
               if ((a_digits[m_used] != 0) ||
-                  (_compareDigits(a_digits, m_used, t_digits, m_used)) > 0) {
-                _absSub(a_digits, abcd_used, t_digits, m_used, a_digits);
+                  (_compareDigits(a_digits, m_used, y_digits, m_used)) > 0) {
+                _absSub(a_digits, abcd_used, y_digits, m_used, a_digits);
               } else {
-                _absSub(t_digits, m_used, a_digits, m_used, a_digits);
+                _absSub(y_digits, m_used, a_digits, m_used, a_digits);
                 a_neg = false;
               }
             } else {
-              _absAdd(a_digits, abcd_used, t_digits, m_used, a_digits);
+              _absAdd(a_digits, abcd_used, y_digits, m_used, a_digits);
             }
             if (b_neg) {
-              _absAdd(b_digits, abcd_used, m_digits, m_used, b_digits);
+              _absAdd(b_digits, abcd_used, x_digits, m_used, b_digits);
             } else if ((b_digits[m_used] != 0) ||
-                (_compareDigits(b_digits, m_used, m_digits, m_used) > 0)) {
-              _absSub(b_digits, abcd_used, m_digits, m_used, b_digits);
+                (_compareDigits(b_digits, m_used, x_digits, m_used) > 0)) {
+              _absSub(b_digits, abcd_used, x_digits, m_used, b_digits);
             } else {
-              _absSub(m_digits, m_used, b_digits, m_used, b_digits);
+              _absSub(x_digits, m_used, b_digits, m_used, b_digits);
               b_neg = true;
             }
           }
           _rsh(a_digits, abcd_used, 1, a_digits);
         } else if ((b_digits[0] & 1) == 1) {
           if (b_neg) {
-            _absAdd(b_digits, abcd_used, m_digits, m_used, b_digits);
+            _absAdd(b_digits, abcd_used, x_digits, m_used, b_digits);
           } else if ((b_digits[m_used] != 0) ||
-                     (_compareDigits(b_digits, m_used, m_digits, m_used) > 0)) {
-            _absSub(b_digits, abcd_used, m_digits, m_used, b_digits);
+                     (_compareDigits(b_digits, m_used, x_digits, m_used) > 0)) {
+            _absSub(b_digits, abcd_used, x_digits, m_used, b_digits);
           } else {
-            _absSub(m_digits, m_used, b_digits, m_used, b_digits);
+            _absSub(x_digits, m_used, b_digits, m_used, b_digits);
             b_neg = true;
           }
         }
         _rsh(b_digits, abcd_used, 1, b_digits);
       }
       while ((v_digits[0] & 1) == 0) {
         _rsh(v_digits, m_used, 1, v_digits);
         if (ac) {
           if (((c_digits[0] & 1) == 1) || ((d_digits[0] & 1) == 1)) {
             if (c_neg) {
               if ((c_digits[m_used] != 0) ||
-                  (_compareDigits(c_digits, m_used, t_digits, m_used) > 0)) {
-                _absSub(c_digits, abcd_used, t_digits, m_used, c_digits);
+                  (_compareDigits(c_digits, m_used, y_digits, m_used) > 0)) {
+                _absSub(c_digits, abcd_used, y_digits, m_used, c_digits);
               } else {
-                _absSub(t_digits, m_used, c_digits, m_used, c_digits);
+                _absSub(y_digits, m_used, c_digits, m_used, c_digits);
                 c_neg = false;
               }
             } else {
-              _absAdd(c_digits, abcd_used, t_digits, m_used, c_digits);
+              _absAdd(c_digits, abcd_used, y_digits, m_used, c_digits);
             }
             if (d_neg) {
-              _absAdd(d_digits, abcd_used, m_digits, m_used, d_digits);
+              _absAdd(d_digits, abcd_used, x_digits, m_used, d_digits);
             } else if ((d_digits[m_used] != 0) ||
-                (_compareDigits(d_digits, m_used, m_digits, m_used) > 0)) {
-              _absSub(d_digits, abcd_used, m_digits, m_used, d_digits);
+                (_compareDigits(d_digits, m_used, x_digits, m_used) > 0)) {
+              _absSub(d_digits, abcd_used, x_digits, m_used, d_digits);
             } else {
-              _absSub(m_digits, m_used, d_digits, m_used, d_digits);
+              _absSub(x_digits, m_used, d_digits, m_used, d_digits);
               d_neg = true;
             }
           }
           _rsh(c_digits, abcd_used, 1, c_digits);
         } else if ((d_digits[0] & 1) == 1) {
           if (d_neg) {
-            _absAdd(d_digits, abcd_used, m_digits, m_used, d_digits);
+            _absAdd(d_digits, abcd_used, x_digits, m_used, d_digits);
           } else if ((d_digits[m_used] != 0) ||
-                     (_compareDigits(d_digits, m_used, m_digits, m_used) > 0)) {
-            _absSub(d_digits, abcd_used, m_digits, m_used, d_digits);
+                     (_compareDigits(d_digits, m_used, x_digits, m_used) > 0)) {
+            _absSub(d_digits, abcd_used, x_digits, m_used, d_digits);
           } else {
-            _absSub(m_digits, m_used, d_digits, m_used, d_digits);
+            _absSub(x_digits, m_used, d_digits, m_used, d_digits);
             d_neg = true;
           }
         }
         _rsh(d_digits, abcd_used, 1, d_digits);
       }
       if (_compareDigits(u_digits, m_used, v_digits, m_used) >= 0) {
         _absSub(u_digits, m_used, v_digits, m_used, u_digits);
         if (ac) {
           if (a_neg == c_neg) {
             var a_cmp_c =
@@ skipping 47 matching lines @@
           }
         } else {
           _absAdd(d_digits, abcd_used, b_digits, abcd_used, d_digits);
         }
       }
       // Exit loop if u == 0.
       var i = m_used;
       while ((i > 0) && (u_digits[i - 1] == 0)) --i;
       if (i == 0) break;
     }
+    if (!inv) {
+      if (s > 0) {
+        _lsh(v_digits, m_used, s, v_digits);
+      }
+      return new _Bigint(false, m_used, v_digits)._toValidInt();
+    }
     // No inverse if v != 1.
     var i = m_used - 1;
     while ((i > 0) && (v_digits[i] == 0)) --i;
     if ((i != 0) || (v_digits[0] != 1)) throw new RangeError("Not coprime");
 
     if (d_neg) {
       if ((d_digits[m_used] != 0) ||
-          (_compareDigits(d_digits, m_used, m_digits, m_used) > 0)) {
-        _absSub(d_digits, abcd_used, m_digits, m_used, d_digits);
+          (_compareDigits(d_digits, m_used, x_digits, m_used) > 0)) {
+        _absSub(d_digits, abcd_used, x_digits, m_used, d_digits);
         if ((d_digits[m_used] != 0) ||
-            (_compareDigits(d_digits, m_used, m_digits, m_used) > 0)) {
-          _absSub(d_digits, abcd_used, m_digits, m_used, d_digits);
+            (_compareDigits(d_digits, m_used, x_digits, m_used) > 0)) {
+          _absSub(d_digits, abcd_used, x_digits, m_used, d_digits);
         } else {
-          _absSub(m_digits, m_used, d_digits, m_used, d_digits);
+          _absSub(x_digits, m_used, d_digits, m_used, d_digits);
           d_neg = false;
         }
       } else {
-        _absSub(m_digits, m_used, d_digits, m_used, d_digits);
+        _absSub(x_digits, m_used, d_digits, m_used, d_digits);
         d_neg = false;
       }
     } else if ((d_digits[m_used] != 0) ||
-               (_compareDigits(d_digits, m_used, m_digits, m_used) > 0)) {
-      _absSub(d_digits, abcd_used, m_digits, m_used, d_digits);
+               (_compareDigits(d_digits, m_used, x_digits, m_used) > 0)) {
+      _absSub(d_digits, abcd_used, x_digits, m_used, d_digits);
       if ((d_digits[m_used] != 0) ||
-          (_compareDigits(d_digits, m_used, m_digits, m_used) > 0)) {
-        _absSub(d_digits, abcd_used, m_digits, m_used, d_digits);
+          (_compareDigits(d_digits, m_used, x_digits, m_used) > 0)) {
+        _absSub(d_digits, abcd_used, x_digits, m_used, d_digits);
       }
     }
     return new _Bigint(false, m_used, d_digits)._toValidInt();
   }
+
+  // Returns 1/this % m, with m > 0.
+  int modInverse(int m) {
+    if (m is! int) throw new ArgumentError(m);
+    if (m <= 0) throw new RangeError(m);
+    if (m == 1) return 0;
+    m = m._toBigint();
+    var t = this;
+    if (t._neg || (t._absCompare(m) >= 0)) {
+      t %= m;
+      t = t._toBigint();
+    }
+    return _binaryGcd(m, t, true);
+  }
+
+  // Returns gcd of abs(this) and abs(other), with this != 0 and other !=0.
+  int gcd(int other) {
+    if (other is! int) throw new ArgumentError(other);
+    return _binaryGcd(this, other._toBigint(), false);
+  }
 }
 
 // Interface for modular reduction.
 class _Reduction {
   // Return the number of digits used by r_digits.
   int _convert(_Bigint x, Uint32List r_digits);
   int _mul(Uint32List x_digits, int x_used,
            Uint32List y_digits, int y_used, Uint32List r_digits);
   int _sqr(Uint32List x_digits, int x_used, Uint32List r_digits);
 
@@ skipping 256 matching lines @@
 
   int _mul(Uint32List x_digits, int x_used,
            Uint32List y_digits, int y_used,
            Uint32List r_digits) {
     var r_used = _Bigint._mulDigits(x_digits, x_used,
                                     y_digits, y_used,
                                     r_digits);
     return _reduce(r_digits, r_used);
   }
 }