Add tests for gcd, modInverse and modPow that also run on dart2js.

runtime/lib/bigint.dart

Index: runtime/lib/bigint.dart
diff --git a/runtime/lib/bigint.dart b/runtime/lib/bigint.dart
index adfb0db4cca73f924008dec248d1c07a09a464d5..77dfea950708797d0535a5583aee63b031fed714 100644
--- a/runtime/lib/bigint.dart
+++ b/runtime/lib/bigint.dart
@@ -267,7 +267,9 @@ class _Bigint extends _IntegerImplementation implements int {
     return r_used;
   }
 
-  // r_digits[0..r_used-1] = x_digits[0..x_used-1] << n.
+  // r_digits[ds..x_used+ds] = x_digits[0..x_used-1] << n
+  // where ds = ceil(n / _DIGIT_BITS)
+  // Doesn't clear digits below ds.
   static void _lsh(Uint32List x_digits, int x_used, int n,
                    Uint32List r_digits) {
     final ds = n ~/ _DIGIT_BITS;
@@ -1404,7 +1406,7 @@ class _Bigint extends _IntegerImplementation implements int {
     if (e == 0) return 1;
     m = m._toBigint();
     final m_used = m._used;
-    final m_used2p4 = 2*m_used + 4;
+    final m_used2p4 = 2 * m_used + 4;
     final e_bitlen = e.bitLength;
     if (e_bitlen <= 0) return 1;
     final bool cannotUseMontgomery = m.isEven || _abs() >= m;
@@ -1562,7 +1564,7 @@ class _Bigint extends _IntegerImplementation implements int {
       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) {
+      while (((x_digits[0] & 1) == 0) && ((y_digits[0] & 1) == 0)) {
         _rsh(x_digits, x_used, 1, x_digits);
         _rsh(y_digits, y_used, 1, y_digits);
         s++;
@@ -1746,10 +1748,11 @@ class _Bigint extends _IntegerImplementation implements int {
       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();
+      // TODO(regis): Make this work correctly:
+      // if (s > 0) {
+      //   _lsh(v_digits, m_used, s, v_digits);
+      // }

[Lasse Reichstein Nielsen, 2015/06/26 08:40:40]

Not sure why this doesn't work - maybe it's because _lsh doesn't clear the low
bits, and because m_used below is too low (it should also include the bits of
s).
For 
  (693 * pow(2, 99)),gcd(609 * pow(2, 99))
which should give 21 * pow(2, 99), it gives just 21.
That would match keeping the low bits at 21 and forgetting the high bits.

I tried changing  _lsh(...)  to  m_used = _dlShiftDigits(...) , but the v_digits
array isn't big enough for that (it has an odd length equal to m_used).

So, quick fix that works is to do << after creating a new bigint.

[regis, 2015/06/26 21:49:46]

That was totally broken. Good that you wrote some gcd tests with even operands.
The problem is that left shift operations need one extra digit (one extra 64-bit
digit on 64-bit platforms), and v_digits does not account for it. Its allocation
length m_len needs adjustment.

Also, the intrinsic _lsh does not clear the low bits, and since we shift in
place, this is not the right one to use.
That was the right idea, but _dlShiftDigits is the wrong one to use, since it is
a digit shift. We need a bit shift, i.e. _lShiftDigits.

The minimum length calculation in _lShiftDigits and _lShift was too conservative
and can be relaxed.

I'll send a cl to Srdjan (cc'ed) shortly.
 
That was the proper workaround. Thanks.

+      return new _Bigint(false, m_used, v_digits)._toValidInt() << s;
     }
     // No inverse if v != 1.
     var i = m_used - 1;