bug in sjcl.bn subtraction?

[xoba]

let's define the function sub as follows:

var sub = function(x,y) {
    var xn = new sjcl.bn(x);
    var yn = new sjcl.bn(y);
    return xn.sub(yn).toString();
}

a correct working example is sub("0x878947B6","0x03AE6A") evaluates to 0x8785994c.

a failing example seems to be sub("0x0B699467","0x8C41121C") evaluates to 0x-8128824b (note the negative sign after 0x). i would have expected 0x-80D77DB5 as the correct answer because:

1. 0x0B699467 is 191468647 in decimal
2. 0x8C41121C is 2353074716 in decimal
3. 191468647 - 2353074716 = -2161606069 in decimal
4. the seemingly incorrect answer would be equivalent to 191468647 - 2353074716 = -2166915659, which is wrong.

am i making a silly mistake somewhere in this? thanks!

[X-Ryl669]

See also #62

[X-Ryl669]

The issue is mainly because of the different base used for splitting the number in limbs, and the representation of the number itself. Since the result is negative (y > x in your example), the big number should return a negative number. However, when computing the operation with a 2 binary complement on 32bits number: 0x0B699467 - 0x8C41121C = 0x7f28824b

Since the computation is done internally in limbs which are 24 bits long and the toString method does not expect underflow, it does not propagate the negative part downward. This results in the low 24 bits value is wrongly used for the result (that is: the 0x-8128824b part) and the high value incorrectly returned (0x-81 should have given a -1 to the low part).

Simply speaking, when you perform 543 - 612, if you start by the last digit and walk up, whenever you encounter a digit that's higher than the digit you try to subtract from, you need to propagate a carry downward, that is, you're computing 3-2 = 1, then 4-1=3, then 5-6=-1. You need to propagate the underflow, by replacing -131 by 031 - 100, that is computing -(100 - 31) = -69. This part is not done in the current code. I think nobody is doing this way anyway since it's too complex, everyone is testing the number before subtracting and subtracting the lower number from the bigger one, and propagating the negative sign to the result if required. This is not done either in the code.

Please notice that the textual representation is kind of wrong anyway since number are usually represented as 2 complements. So the actual string representation for a this number should be in 2 complement: 0x1 7f28824b. Usually, one would expect a multiple of 32 bits for the number representation, so you'd have to extend the sign: 0xffffffff 7f28824b

I'm not sure what is the correct fix here (where to fix it, either in sub or in toString). For example, this code gives almost the good result:

var sub = function(x,y) {
    var xn = new sjcl.bn(x),
          yn = new sjcl.bn(y);
   if (yn.greaterEquals(xn)) return yn.sub(xn).mul(-1).toString();
   return xn.sub(yn).toString();
}

I've a version of serialization to string that's giving the expected result because it's propagating the signs

function strOut(z)
{
    var out="", v, i = 0, j = 0, l = z.limbs, r = z.radix, n = z.limbs.length * r / 32, o = 0, t = 0;
    for (i = 0; i < n; i++) {
        t += r;
        v = (l[j] >> o) + ((j < l.length - 1 ? l[j+1] : 0) * (1 << t));
        o += 32 - r;
        if (t + r <= 32) j++;
        if (o >= 32) o -= 32;
        j++; t -= 32;
        out = (v+0xF00000000).toString(16).substr(-8) + out;
        if (j > l.length) break;
    }
    return out;
}

In your example, it's returning ffffffff7f28824b which is the correct 64bits (2 complement) representation of the number.

I need some advice about where to fix this bug. I wonder it's in the subM method IMHO.

[X-Ryl669]

So far, the best option that does also solve #62 is to replace the method subM by:

/** this -= that.  Does not normalize. */
  subM: function(that) {
    if (typeof(that) !== "object") { that = new this._class(that); }
    var inv = that.greaterEquals(this);   
    var i, l=this.limbs, ll=that.limbs;
    for (i=l.length; i<ll.length; i++) {
      l[i] = 0;
    }
    for (i=0; i<ll.length; i++) {
      l[i] = inv ? (ll[i] - l[i]) : (l[i] - ll[i]);
    }
    if (inv && l.length) l[l.length - 1] = -l[l.length - 1];
    return this;
},