int - npm Package Compare versions

Comparing version 0.0.1 to 0.0.3

int.js

@@ -10,3 +10,4 @@
 
-    if(num instanceof Int){
+    // copy existing Int object
+    if (num instanceof Int){
         self._s = num._s;
@@ -18,9 +19,23 @@ self._d = num._d.slice();
     // sign
-    self._s = (num += '').charAt(0) === '-';
+    self._s = ((num += '').charAt(0) === '-') ? 1 : 0;
 
-    // remove any leading - or +
+    // digits
+    self._d = [];
+
+    // remove any leading - or + as well as other invalid characters
     num = num.replace(/[^\d]/g, '');
 
-    // _d is the array of numbers
-    for(var i = (num = self._d = num.split('')).length; i; num[--i] = +num[i]);
+    // _d is the array of single digits making up the number
+    var ln = num.length;
+    for (var i=0 ; i<ln ; ++i) {
+        self._d.push(+num[i]);
+    }
+
+    trim_zeros(self);
+
+    // zeros are normalized to positive
+    // TODO (shtylman) consider not doing this and only checking in toString?
+    if (self._d.length === 0) {
+        self._s = 0;
+    }
 };
@@ -31,4 +46,5 @@
     var self = this;
+    var num = ensure_int(num);
 
-    if(self._s !== (num = Int(num))._s) {
+    if(self._s != num._s) {
         num._s ^= 1;
@@ -38,18 +54,51 @@ return self.sub(num);
 
-    // new output number
-    var out = Int(self);
+    // a will be the smaller number
+    if (self._d.length < num._d.length) {
+        var a = self._d;
+        var b = num._d;
+        var out = Int(num);
+    }
+    else {
+        var a = num._d;
+        var b = self._d;
+        var out = Int(self);
+    }
 
-    var a = out._d;
-    var b = num._d;
     var la = a.length;
     var lb = b.length;
 
-    la != lb && ((lb = la - lb) > 0 ? zeroes(b, lb, 1) : zeroes(a, -lb, 1));
+    // clone the larger number
+    var res = out._d;
 
-    var i = (la = a.length) == (lb = b.length) ? a.length : ((lb = la - lb) > 0 ? zeroes(b, lb) : zeroes(a, -lb)).length;
+    var carry = 0;
+    for (var i = lb - 1, j = la - 1; i >= 0, j >= 0 ; --i, --j) {
+        res[i] += carry + a[j];
+        carry = 0;
 
-    for(var r = 0; i; r = (a[--i] = a[i] + b[i] + r) / 10 >>> 0, a[i] %= 10);
+        if (res[i] >= 10) {
+            res[i] -= 10;
+            carry = 1;
+        }
+    }
 
-    r && a.unshift(r);
+    // carry the rest of the way
+    for (; i >= 0 ; --i) {
+        res[i] += carry;
+        carry = 0;
+        if (res[i] >= 10) {
+            res[i] -= 10;
+            carry = 1;
+        }
 
+        // no carry, rest of the number will be unchanged
+        if (carry === 0) {
+            break;
+        }
+    }
+
+    // remaining carry?
+    if (carry > 0) {
+        res.unshift(1);
+    }
+
     return out;
@@ -61,3 +110,6 @@ }
 
-    if(self._s != (num = Int(num))._s) {
+    // some operations are destructive
+    var num = Int(num);
+
+    if(self._s != num._s) {
         num._s ^= 1;
@@ -67,47 +119,103 @@ return this.add(num);
 
-    var out = Int(self);
+    // make a the smaller number
+    var c = self._d.length < num._d.length;
+    var a = c ? self._d : num._d;
+    var b = c ? num._d : self._d;
 
-    // make a the larger number
-    var c = out.abs().lt(num.abs());
-    var a = c ? out._d : num._d;
-    var b = c ? num._d : out._d;
-
     var la = a.length;
     var lb = b.length;
 
-    // pad shorter number with 0's
-    la != lb && zeroes(a, lb - la, 1);
+    var out = Int((c) ? num : self);
+    out._s = num._s & self._s; // ??
+    var res = out._d;
 
-    // prep borrow by subtracting away all we need
-    for (var i=lb-1 ; i>0 ; --i) {
-        if (b[i] < 0 || a[i] > b[i]) {
-            b[i] += 10;
-            b[i-1] -= 1;
+    // basic subtraction for common size
+    var borrow = 0;
+    for (var i = lb - 1, j = la - 1; i >= 0, j >= 0 ; --i, --j) {
+        res[i] -= a[j] + borrow;
+        borrow = 0;
+
+        if (res[i] < 0) {
+            res[i] += 10;
+            borrow = 1;
         }
     }
 
-    // perform actual subtraction
-    for (var i=0 ; i<lb ; ++i) {
-        b[i] -= a[i];
+    // carry the rest of the way
+    for (; i >= 0 ; --i) {
+        res[i] -= borrow;
+        borrow = 0;
+        if (res[i] < 0) {
+            res[i] += 10;
+            borrow = 1;
+        }
+
+        // no carry, rest of the number will be unchanged
+        if (borrow === 0) {
+            break;
+        }
     }
 
+    // flip the sign if sub num was larger
     c && (out._s ^= 1);
-    out._d = b;
+
+    trim_zeros(out);
+
+    // TODO the subtraction should just be smarter
+    if (out._d.length === 0) {
+        out._s = 0;
+    }
+
     return out;
 };
 
-Int.prototype.mul = function(n) {
-    var o = Int(this);
-    var r = o._d.length >= (n = Int(n))._d.length;
-    var a = (r ? o : n)._d;
-    var b = (r ? n : o)._d;
+Int.prototype.mul = function(num) {
+    var self = this;
+
+    var r = self._d.length >= (num = Int(num))._d.length;
+    var a = (r ? self : num)._d;
+    var b = (r ? num : self)._d;
+
     var la = a.length;
     var lb = b.length;
-    var x = Int(), j, s;
 
-    for(var i = lb; i; r && s.unshift(r), x.set(x.add(Int(s.join(''))))) {
-        for(s = (new Array(lb - --i)).join('0').split(''), r = 0, j = la; j; r += a[--j] * b[i], s.unshift(r % 10), r = (r / 10) >>> 0);
+    var sum = Int();
+    var zeros = [];
+
+    // loop for smaller number
+    for (var i = lb - 1 ; i >= 0 ; --i) {
+        var out = Int();
+
+        // insert proper number of trailing 0s
+        var val = out._d = out._d.concat(zeros);
+
+        // reset carry
+        var carry = 0;
+
+        // top number
+        for (var j = la - 1; j >= 0; --j) {
+            // multiplication result
+            var mul = b[i] * a[j] + carry;
+
+            // this is the single digit we keep
+            var res = mul % 10;
+
+            // carry amount
+            carry = Math.floor(mul / 10);
+
+            // insert the number into our new integer
+            val.unshift(res);
+        }
+
+        // apply any remaining carry
+        if (carry) {
+            val.unshift(carry);
+        }
+
+        sum = sum.add(out);
+        zeros.push(0);
     }
-    o._s = o._s != n._s, o._f = ((r = la + lb - o._f - n._f) >= (j = (o._d = x._d).length) ? zeroes(o._d, r - j + 1, 1).length : j) - r;
-    return o;
+
+    sum._s = self._s ^ num._s;
+    return sum;
 };
@@ -118,19 +226,61 @@
 
-    if((num = Int(num)) == '0') {
+    // copy since we change sign of num
+    var num = Int(num);
+
+    if(num == '0') {
         throw new Error('Division by 0');
     }
-    else if(this == '0') {
+    else if(self == '0') {
         return Int();
     }
 
-    var out = Int(0);
-    var zero = Int(0);
+    // copy since we do destructive things
+    var numerator = self._d.slice();
 
-    // TODO (shtylman) changeme from naive implementation
-    while(zero.lt(self)) {
-        out = out.add(1);
-        zero = zero.add(num);
+    var quo = Int();
+    quo._s = self._s ^ num._s;
+
+    // normalize num to positive number
+    num._s = 0;
+
+    // remainder from previous calculation
+    var rem = Int();
+
+    while (numerator.length) {
+        // long division
+        // shift numbers off the numerator until we have achieved size
+        // every number after the first causes a 0 to be inserted
+        // numbers shifted in from the remainder should not cause 0 insertion
+
+        var c = 0;
+        while (numerator.length && rem.lt(num)) {
+            if (c++ > 0) {
+                quo._d.push(0);
+            }
+
+            // shift a number from numerator to our running num
+            rem._d.push(numerator.shift());
+        }
+
+        var count = 0;
+        while(rem.gte(num) && ++count) {
+            rem = rem.sub(num);
+        }
+
+        if (count === 0) {
+            quo._d.push(0);
+            break;
+        }
+
+        quo._d.push(count);
     }
 
-    return out;
+    var rem_prime = rem.add(5);
+
+    // add 1 if negative to 'truncate'
+    if (quo._s && (rem_prime._d[0] >= 5 || rem_prime._d.length > rem._d.length)) {
+        quo = quo.sub(1);
+    }
+
+    return trim_zeros(quo);
 };
@@ -159,16 +309,16 @@
 /// -1 if self < n, 0 if self == n, 1 if self > n
-Int.prototype.cmp = function(n) {
+Int.prototype.cmp = function(num) {
     var self = this;
-    var b = Int(n);
+    var num = ensure_int(num);
 
-    if (self._s != b._s) {
+    if (self._s != num._s) {
         return self._s ? -1 : 1;
     }
 
-    var la = self._d.length;
-    var lb = b._d.length;
-
     var a = self._d;
-    var b = b._d;
+    var b = num._d;
 
+    var la = a.length;
+    var lb = b.length;
+
     if (la != lb) {
@@ -178,4 +328,3 @@ return ((la > lb) ^ self._s) ? 1 : -1;
 
-    var l = Math.min(la, lb);
-    for (var i = 0; i < l; ++i) {
+    for (var i = 0; i < la; ++i) {
         if (a[i] != b[i]) {
@@ -186,4 +335,4 @@ return ((a[i] > b[i]) ^ self._s) ? 1 : -1;
 
-    var r = [-1, 1];
-    return la != lb ? r[(la > lb) ^ self._s] : 0;
+    // no differences
+    return 0;
 };
@@ -205,3 +354,3 @@
     var self = this;
-    return (self._s ? '-' : '') + self._d.join('');
+    return (self._s && self._d.length ? '-' : '') + ((self._d.length) ? self._d.join('') : '0');
 };
@@ -235,9 +384,20 @@
 
-function zeroes(n, l, t) {
-    var s = ['push', 'unshift'][t || 0];
-    for(++l; --l; n[s](0));
-    return n;
-};
+function ensure_int(val) {
+    if (val instanceof Int) {
+        return val;
+    }
 
+    return Int(val);
+}
+
+/// remove leading 0's from the int
+function trim_zeros(int) {
+    while (int._d.length && int._d[0] === 0) {
+        int._d.shift();
+    }
+
+    return int;
+}
+
 module.exports = Int;
 

package.json

@@ -5,3 +5,3 @@ {
   "description": "arbitrary precision integer and library in pure javascript",
-  "version": "0.0.1",
+  "version": "0.0.3",
   "repository": {
@@ -8,0 +8,0 @@ "type": "git",

New alerts

Major refactor

Supply chain risk

Package has recently undergone a major refactor. It may be unstable or indicate significant internal changes. Use caution when updating to versions that include significant changes.

Found 1 instance in 1 package

Fixed alerts

No README

Quality

Package does not have a README. This may indicate a failed publish or a low quality package.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

15409

increased by114.1%

Number of package files

14

increased by133.33%

Lines of code

438

increased by86.38%

Number of medium quality alerts

0

decreased by-100%

Number of lines in readme file

83

increased byInfinity%

Worsened metrics

Number of medium supply chain risk alerts

1

increased byInfinity%

No dependency changes