bn.js - npm Package Compare versions

Comparing version 1.1.1 to 1.2.1

1.js

@@ -1,7 +0,8 @@
-var bn = require('./');
+var BN = require('./');
 
-var a1 = new bn('012345678901234567890123456789012345678901234567890', 10);
-
-var as1 = a1.mul(a1).iaddn(0xdeadbeef);
-
-console.log(as1.div(a1));
+var a = new BN("6582018229284824168619876730229320890292528855852623664389292032");
+var b = new BN("730750818665451459101842416358132502628711530497");
+console.log(b.words);
+var q = a.div(b);
+var m = a.mod(b);
+console.log(q, m);

lib/bn.js

@@ -222,3 +222,6 @@ // Utils
     this.imuln(limbPow);
-    this.words[0] += word;
+    if (this.words[0] + word < 0x4000000)
+      this.words[0] += word;
+    else
+      this._iaddn(word);
   }
@@ -233,3 +236,6 @@
     this.imuln(pow);
-    this.words[0] += word;
+    if (this.words[0] + word < 0x4000000)
+      this.words[0] += word;
+    else
+      this._iaddn(word);
   }
@@ -607,20 +613,10 @@ };
   for (var i = 0; i < b.length; i++) {
-    var r = a.words[i] - b.words[i] - carry;
-    if (r < 0) {
-      r += 0x4000000;
-      carry = 1;
-    } else {
-      carry = 0;
-    }
-    this.words[i] = r;
+    var r = a.words[i] - b.words[i] + carry;
+    carry = r >> 26;
+    this.words[i] = r & 0x3ffffff;
   }
   for (; carry !== 0 && i < a.length; i++) {
-    var r = a.words[i] - carry;
-    if (r < 0) {
-      r += 0x4000000;
-      carry = 1;
-    } else {
-      carry = 0;
-    }
-    this.words[i] = r;
+    var r = a.words[i] + carry;
+    carry = r >> 26;
+    this.words[i] = r & 0x3ffffff;
   }
@@ -1022,2 +1018,8 @@
   }
+
+  // Add without checks
+  return this._iaddn(num);
+};
+
+BN.prototype._iaddn = function _iaddn(num) {
   this.words[0] += num;
@@ -1080,2 +1082,95 @@
 
+BN.prototype._ishlnadd = function _ishlnadd(num, shift) {
+  assert(!num.sign);
+  if (this.sign) {
+    this.sign = false;
+    this._ishlnsub(num, shift);
+    this.sign = !this.sign;
+    return this;
+  }
+
+  // Bigger storage is needed
+  var len = num.length + shift + 1;
+  if (this.words.length < len) {
+    var t = new Array(len);
+    for (var i = 0; i < this.length; i++)
+      t[i] = this.words[i];
+    this.words = t;
+  } else {
+    i = this.length;
+  }
+
+  // Zeroify rest
+  this.length = Math.max(this.length, len);
+  for (; i < this.length; i++)
+    this.words[i] = 0;
+
+  var carry = 0;
+  for (var i = 0; i < num.length; i++) {
+    var w = this.words[i + shift] + num.words[i]  + carry;
+    carry = w >> 26;
+    this.words[i + shift] = w & 0x3ffffff;
+  }
+  for (; i < this.length - shift; i++) {
+    var w = this.words[i + shift] + carry;
+    carry = w >> 26;
+    this.words[i + shift] = w & 0x3ffffff;
+  }
+
+  return this.strip();
+};
+
+BN.prototype._ishlnsub = function _ishlnsub(num, shift) {
+  assert(!num.sign);
+  if (this.sign) {
+    this.sign = false;
+    this._ishlnadd(num, shift);
+    this.sign = !this.sign;
+    return this;
+  }
+
+  // Bigger storage is needed
+  var len = num.length + shift;
+  if (this.words.length < len) {
+    var t = new Array(len);
+    for (var i = 0; i < this.length; i++)
+      t[i] = this.words[i];
+    this.words = t;
+  } else {
+    i = this.length;
+  }
+
+  // Zeroify rest
+  this.length = Math.max(this.length, len);
+  for (; i < this.length; i++)
+    this.words[i] = 0;
+
+  var carry = 0;
+  for (var i = 0; i < num.length; i++) {
+    var w = this.words[i + shift] - num.words[i]  + carry;
+    carry = w >> 26;
+    this.words[i + shift] = w & 0x3ffffff;
+  }
+  for (; i < this.length - shift; i++) {
+    var w = this.words[i + shift] + carry;
+    carry = w >> 26;
+    this.words[i + shift] = w & 0x3ffffff;
+  }
+
+  if (carry === 0)
+    return this.strip();
+
+  // Subtraction overflow
+  assert(carry === -1);
+  carry = 0;
+  for (var i = 0; i < this.length; i++) {
+    var w = -this.words[i] + carry;
+    carry = w >> 26;
+    this.words[i] = w & 0x3ffffff;
+  }
+  this.sign = true;
+
+  return this.strip();
+};
+
 BN.prototype._wordDiv = function _wordDiv(num, mode) {
@@ -1087,60 +1182,59 @@ var shift = this.length - num.length;
 
-  var q = mode !== 'mod' && new BN(0);
-  var sign = false;
+  // Normalize
+  var bhi = b.words[b.length - 1];
+  for (var shift = 0; bhi < 0x2000000; shift++)
+    bhi <<= 1;
+  if (shift !== 0) {
+    b = b.shln(shift);
+    a.ishln(shift);
+    bhi = b.words[b.length - 1];
+  }
 
-  // Approximate quotient at each step
-  while (a.length > b.length) {
-    // NOTE: a.length is always >= 2, because of the condition .div()
-    var hi = a.words[a.length - 1] * 0x4000000 + a.words[a.length - 2];
-    var sq = (hi / b.words[b.length - 1]);
-    var sqhi = (sq / 0x4000000) | 0;
-    var sqlo = sq & 0x3ffffff;
-    sq = new BN(null);
-    sq.words = [ sqlo, sqhi ];
-    sq.length = 2;
+  // Initialize quotient
+  var m = a.length - b.length;
+  var q;
 
-    // Collect quotient
-    var shift = (a.length - b.length - 1) * 26;
-    if (q) {
-      var t = sq.shln(shift);
-      if (a.sign)
-        q.isub(t);
-      else
-        q.iadd(t);
-    }
+  if (mode !== 'mod') {
+    q = new BN(null);
+    q.length = m + 1;
+    q.words = new Array(q.length);
+    for (var i = 0; i < q.length; i++)
+      q.words[i] = 0;
+  }
 
-    sq = sq.mul(b).ishln(shift);
-    if (a.sign)
-      a.iadd(sq)
-    else
-      a.isub(sq);
+  var diff = a.clone()._ishlnsub(b, m);
+  if (!diff.sign) {
+    a = diff;
+    if (q)
+      q.words[m] = 1;
   }
-  // At this point a.length <= b.length
-  while (a.ucmp(b) >= 0) {
-    // NOTE: a.length is always >= 2, because of the condition above
-    var hi = a.words[a.length - 1];
-    var sq = new BN((hi / b.words[b.length - 1]) | 0);
-    var shift = (a.length - b.length) * 26;
 
-    if (q) {
-      var t = sq.shln(shift);
-      if (a.sign)
-        q.isub(t);
-      else
-        q.iadd(t);
-    }
+  var st = new BN(null);
+  st.words = new Array(b.length + 1);
+  st.length = 0;
+  for (var j = m - 1; j >= 0; j--) {
+    var qj = a.words[b.length + j] * 0x4000000 + a.words[b.length + j - 1];
 
-    sq = sq.mul(b).ishln(shift);
+    // NOTE: (qj / bhi) is (0x3ffffff * 0x4000000 + 0x3ffffff) / 0x2000000 max
+    // (0x7ffffff)
+    qj = Math.min((qj / bhi) | 0, 0x3ffffff);
 
-    if (a.sign)
-      a.iadd(sq);
-    else
-      a.isub(sq);
+    for (var i = 0; i < b.length; i++)
+      st.words[i] = b.words[i];
+    st.length = b.length;
+    a._ishlnsub(st.imuln(qj), j);
+    while (a.sign) {
+      qj--;
+      a._ishlnadd(b, j);
+    }
+    if (q)
+      q.words[j] = qj;
   }
+  if (q)
+    q.strip();
+  a.strip();
 
-  if (a.sign) {
-    if (q)
-      q.isubn(1);
-    a.iadd(b);
-  }
+  // Denormalize
+  if (shift !== 0)
+    a.ishrn(shift);
   return { div: q ? q : null, mod: a };
@@ -1147,0 +1241,0 @@ };

package.json

 {
   "name": "bn.js",
-  "version": "1.1.1",
+  "version": "1.2.1",
   "description": "Big number implementation in pure javascript",
@@ -5,0 +5,0 @@ "main": "lib/bn.js",

test/bn-test.js

@@ -33,2 +33,6 @@ var assert = require('assert');
     assert.equal(new BN(base36, 36).toString(36), base36);
+
+    assert(
+      new BN('6582018229284824168619876730229320890292528855852623664389292032')
+          .words[0] < 0x4000000);
   });
@@ -35,0 +39,0 @@

New alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Fixed alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

85882

increased by2.9%

Lines of code

2563

increased by3.47%

No dependency changes