Estimate quotient digit in Bigint division using an integer division instead of

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 28 matching lines @@
  */
 
 class _Bigint extends _IntegerImplementation implements int {
   // Bits per digit.
   static const int DIGIT_BITS = 32;
   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_BASE = 1 << DIGIT2_BITS;
   static const int DIGIT2_MASK = (1 << DIGIT2_BITS) - 1;
 
   // Allocate extra digits so the bigint can be reused.
   static const int EXTRA_DIGITS = 4;
 
-  // Floating-point unit integer precision.
-  static const int FP_BITS = 52;
-  static const int FP_BASE = 1 << FP_BITS;
-  static const int FP_D1 = FP_BITS - DIGIT_BITS;
-  static const int FP_D2 = 2 * DIGIT_BITS - FP_BITS;
-
   // Min and max of non bigint values.
   static const int MIN_INT64 = (-1) << 63;
   static const int MAX_INT64 = 0x7fffffffffffffff;
 
   // Bigint constant values.
   // Note: Not declared as final in order to satisfy optimizer, which expects
   // constants to be in canonical form (Smi).
   static _Bigint ZERO = new _Bigint();
   static _Bigint ONE = new _Bigint()._setInt(1);
 
@@ skipping 769 matching lines @@
         q._used = 0;
       }
       if (r != null) {
         _copyTo(r);
       }
       return;
     }
     if (r == null) {
       r = new _Bigint();
     }
-    var y = new _Bigint();
-    var nsh = DIGIT_BITS - _nbits(a._digits[a._used - 1]);  // normalize modulus
+    var y = new _Bigint();  // Normalized modulus.
+    var nsh = DIGIT_BITS - _nbits(a._digits[a._used - 1]);
     if (nsh > 0) {
       a._lShiftTo(nsh, y);
       _lShiftTo(nsh, r);
     }
     else {
       a._copyTo(y);
       _copyTo(r);
     }
     // We consider this and a positive. Ignore the copied sign.
     y._neg = false;
     r._neg = false;
     var y_used = y._used;
     var y0 = y._digits[y_used - 1];
     if (y0 == 0) return;
-    var yt = y0*(1 << FP_D1) + ((y_used > 1) ? y._digits[y_used - 2] >> FP_D2 : 0);
-    var d1 = FP_BASE/yt;
-    var d2 = (1 << FP_D1)/yt;
-    var e = 1 << FP_D2;
+    var yt = y0 >> 1;  // Chop off one bit, see below. y is normalized: yt != 0.
     var i = r._used;
     var j = i - y_used;
     _Bigint t = (q == null) ? new _Bigint() : q;
 
     y._dlShiftTo(j, t);
 
     if (r._compareTo(t) >= 0) {
       r._digits[r._used++] = 1;
       r._subTo(t, r);
     }
     ONE._dlShiftTo(y_used, t);
-    t._subTo(y, y);  // "negative" y so we can replace sub with _am later
+    t._subTo(y, y);  // Negate y so we can replace sub with _am later.
     while (y._used < y_used) {
       y._digits[y._used++] = 0;
     }
     while (--j >= 0) {
-      // Estimate quotient digit
-      var qd = (r._digits[--i] == y0)
-          ? DIGIT_MASK
-          : (r._digits[i]*d1 + (r._digits[i - 1] + e)*d2).floor();
-      if ((r._digits[i] += y._amc(0, qd, r, j, 0, y_used)) < qd) {  // Try it out
+      // Estimate quotient digit.
+      var qd;
+      if (r._digits[--i] == y0) {
+        qd = DIGIT_MASK;
+      } else {
+        // Chop off one bit, since a Mint cannot hold 2 DIGITs.
+        qd = ((r._digits[i] << (DIGIT_BITS - 1)) |
+              (r._digits[i - 1] >> 1)) ~/ yt;
+        if (qd > DIGIT_MASK) {
+          qd = DIGIT_MASK;
+        }
+      }
+      if ((r._digits[i] += y._am(0, qd, r, j, y_used)) < qd) {  // Try it out.
         y._dlShiftTo(j, t);
         r._subTo(t, r);
         while (r._digits[i] < --qd) {
           r._subTo(t, r);
         }
       }
     }
     if (q != null) {
       r._drShiftTo(y_used, q);
       if (_neg != a._neg) {
         ZERO._subTo(q, q);
       }
     }
     r._used = y_used;
     r._clamp();
     if (nsh > 0) {
-      r._rShiftTo(nsh, r);  // Denormalize remainder
+      r._rShiftTo(nsh, r);  // Denormalize remainder.
     }
     if (_neg) {
       ZERO._subTo(r, r);
     }
   }
 
   int get _identityHashCode {
     return this;
   }
   int operator ~() {
@@ skipping 429 matching lines @@
   void _sqrTo(_Bigint x, _Bigint r) {
     x._sqrTo(r);
     _reduce(r);
   }
 
   void _mulTo(_Bigint x, _Bigint y, _Bigint r) {
     x._mulTo(y, r);
     _reduce(r);
   }
 }