Feature request: bitLength

[tejainece]

Hej,

Thanks for the great library! Would be nice if provides bitLength.

[peterolson]

Can you comment on the use case for this? It is a little bit unusual to implement since the underlying representation of big integers is not binary.

[tejainece]

It can be useful in a number of cases including when we want to get the big integer as bytes, it is useful to know the number of bytes it will fit into. For example,

https://github.com/desktop-dart/fatint/blob/master/lib/src/js/js.dart#L185

[peterolson]

Currently there is no method to get bigInts as bytes (unless you count base conversion), so you would have to implement the byte functionality yourself anyways. Is there a reason to specifically add bitLength without any other bit related functionality?

[tejainece]

I am wrapping your library to provide big integer functionality on browser for Dart (Dart supports big integer on Dart VM by default). The Dart library I shared with you above is thin wrapper around your library. So i am using your API to get bytes. Since, you provide shiftLeft, shiftRight, and, or, not and xor most of the bit operations are covered.

I did write a very inefficient way to calculate bitLength using shiftRight and isZero api you provide. You probably might be able to do it much much faster.

https://github.com/desktop-dart/fatint/blob/59c8e12d3af04db30093558f2e4856e25e2ebe30/lib/src/js/js.dart#L337

[Yaffle]

bigInt.bitLength = function (n) {
  var integerLogarithm = function (value, base) {
    if (base.compareTo(value) <= 0) {
      var tmp = integerLogarithm(value, base.square(base));
      var p = tmp.p;
      var e = tmp.e;
      var t = p.multiply(base);
      return t.compareTo(value) <= 0 ? {p: t, e: e * 2 + 1} : {p: p, e: e * 2};
    }
    return {p: bigInt(1), e: 0};
  };
  n = bigInt(n);
  if (n.compareTo(bigInt(0)) < 0) {
    n = n.negate().subtract(bigInt(1));
  }
  if (n.compareTo(bigInt(0)) === 0) {
    return bigInt(0);
  }
  return bigInt(integerLogarithm(n, bigInt(2)).e).add(bigInt(1));
};

[username1565]

Fixed, and added - here: https://codepen.io/anon/pen/VxdvjO https://github.com/peterolson/BigInteger.js/issues/132

[username1565]

Just use:

var positive = bigInt('12297829382473034410');
var negative = bigInt('-12297829382473034410');
document.write(
    '<br><br>bitstring '+positive.toString()+' (64): '+positive.toString(2)+
    '<br>bitlength '+positive.toString()+' (64): '+positive.toString(2).length+
    '<br><br>bitstring '+negative.toString()+' (64): '+negative.toString(2)+
    '<br>bitlength '+negative.toString()+' (64): '+(negative.toString(2).length-1) //discard minus
);

Or, if you have negative numbers, you can using simply function:

function bitlength(){
    if(this.isNegative){return this.toString(2).length-1;} //discard minus
    else{return this.toString(2).length;}
}

Remember that, -2 numbers usually have fixed ones bits in beginning:

-2 = 1111111111111111111111111111111111111111111111111111111111111110 (64 bits, 8 bytes)
-2 = 11111111111111111111111111111110 (32 bits, 4 bytes)
-2 = 1111111111111110 (16 bits, 2 bytes)
-2 = 11111110 (8 bits, 1 bytes)

and this means, -x (bits) = (2^bits + (-x)). For example:

-2 (64) = 2^64 + (-2) = 2^64 - 2 = 18446744073709551614 = 
10000000000000000000000000000000000000000000000000000000000000000
(this have 65 bits, and NOT 64 bits number) -10 (-2 to bin) =
1111111111111111111111111111111111111111111111111111111111111110
(-2, as 64 bit number, 8 bytes)

[courteous]

Hello Peterolson,

your library is really useful and i would like to thank you for that. I would need to implement one of the getBitLength method as well on top of the BigInteger class, Can you advise if you are planning to add this method to the library. I have seen already 2 method i.e. the one form Yaffle, the one form tejainece i.e.: Is there any problem with those or you just do not want to add the BitLength to library?

 /// Returns number of bits required to represent [this].
  int get bitLength {
    if(_value.isZero()) return 0;

    BigInteger data = _value;
    int ret = 0;
    while(!data.isZero()) {
      ret++;
      data = data.shiftRight(1);
    }
    return ret;
}

[peterolson]

Since this has been requested so much now, I went ahead and put in the solution by @Yaffle in commit 886ecf0c00a8a4e576514213389b6f63e4c9ea66.

[courteous]

peterolson many many many thanks for this.

[ppKrauss]

Hi @Yaffle or @peterolson , there are a reference (to add as comment in the code) with the source of the algorithm? It is at Wikipedia's Discrete Logarithms?

[Yaffle]

@ppKrauss , don't think so, this is some variation of the binary search...

there is also another implementation at https://programmingpraxis.com/contents/standard-prelude/

[ppKrauss]

Oops, performance problems, the this.toString(2).length is 2x or more faster (!) tham any "pure javascript" solution... Without effective WebAssembly solutiom, I suggest to use toString().

PS: @Yaffle check https://stackoverflow.com/q/55355184/287948

---

Testing

  function ilog2_str(n) {  // faster!
     return n.toString(2).length - 1
  }

  function ilog2_optim(value, base=2n) { // supposing the best that we can do...
      if (base  <= value) {
          let i = ilog2_optim(value, base**2n);
          let t = i.p*base
          return (t <= value)
            ? { p: t,   e: i.e*2n + 1n }
            : { p: i.p, e: i.e*2n }
      }
      return { p: 1n, e: 0n };
  }

TESTING WITH time node file.js algorithm

// CONFIGS:
  var V = 2n**1024n;  // 64, 1024 ... same
  let maxLoops=123456;
  let STP = 9999999n;  

var mode=process.argv[2]
var x=0
for (var loops=0; loops<maxLoops; loops++) {
  V = V + STP;
  switch (mode) {
    case 'str':
      x += ilog2_str(V)
      break;
    case 'optim':
      x += Number( ilog2_optim(V).e )
      break;
    default: mode="INVALID NAME: use str or optim"
  }
}
console.log( "Performance of ",mode)
console.log(" Sum after "+loops+" loops:",x)
console.log( " Average bits of values: ", Math.ceil(x/loops) )

RESULTS: for ~120000 loops

algorithm	bits of x	time (s)	time to ilog2(x)
optim1	64	0.451	0.297
str	64	0.183	0.029
(nothing)	-	0.15	-
optim1	1024	0.660	0.51
str	1024	0.385	0.24

[Yaffle]

for small numbers (those, who can be converted to Number), you could also try

let guess = Math.floor(Math.log(Number(bigint)) * Math.LOG2E);
if (guess < 48) {
  // it is always correct
  return guess;
}
if (guess < 1 / 0) {
  // small enough
  if ((bigint >> BigInt(guess)) == 0n) { // please, check it
     guess -= 1;
  }
  return guess;
}
//... switch to ilog2_optim with base=2n**1024n, divide, go to small

[ppKrauss]

for small numbers (those, who can be converted to Number), you could also try

let guess = Math.floor(Math.log(Number(bigint)) * Math.LOG2E);

The time to check is so long, the cost of Math.log (or Math.log2) is near the same (only ~15% faster) to do all work in one step, by toString... BigInt is used for big things, not make sense to check small ones, the probability is low.

---

Tested with numbers with avg 45 bits, 553827454 loops:

• empty time: ~2s
• Math.log: 3.82s - 2s = 1,8s (with no if/else logic)
• Math.log2: 4.21s - 2s = 2.2s
• toString: 4.18s - 2s = 2,2s

Conclusion: better to use directly toString, without any "check small" logic.

Cost to check numbers with avg 200 bits:

• Math.log: 3.9s - 2s = 1,9s (with no if/else logic)
• toString: 7.2s - 2s = 5s

Conclusion: the "check small" add's ~40% (or more) of time in the by toString operation.

[Yaffle]

This is very strange... toString was never faster for me

[ppKrauss]

This is very strange... toString was never faster for me

Hum... Let's use a consensual online benchmark tool... I not use... Do you use something like http://jsben.ch ?

Perhaps other options as console.time(), but is local... see https://stackoverflow.com/a/17943511/287948

---

Numbers with avgBits=200 , testing 12345678 loops by console.time, time in ms:

ilog2_str	ilog2_optim	log
7610	57470	3010
7950	61780	3040

Numbers with avgBits=32 , testing 12345678 loops by console.time, time in ms:

ilog2_str	log
3990	3190
3970	3200

Conclusion: for small numbers consumes near the same time (!), for big numbers only lost time checking... Not make sense to use a check.

... Even with "check small" logic consuming half of toString() time, is better to use only toString(), because in average we have more big numbers tham little numbers, so lost 50% or more of toString() performance time only checking.

[Yaffle]

@ppKrauss , well. you are right, for some reasons, n.toString(2).length - 1 is very good for many cases... It only becomes slower for very very big strings and if to use binary operators... and it is a slightly slower for small numbers.

Another thing that is even faster:

  function ilog2_str16(n) { 
    var s = n.toString(16);
    var c = s.charCodeAt(0);
    var e = 0;
    if (c >= 65 || c >= 48 + 8) {
      e = 3;
    } else if (c >= 48 + 4) {
      e = 2;
    } else if (c >= 48 + 2) {
      e = 1;
    } else {
      e = 0;
    }
    return (s.length - 1) * 4 + e;
  }

But of course, I do not think it is worth to use it in the good code. In fact, the time complexity should be the same for all versions.

[Yaffle]

@ppKrauss, my own tests show that Math.log() is faster for small numbers or almost as fast as BigInt#toString(), the check is not significant, and if to implement the optim variant using bitwise operations, then it will be a bit faster that BigInt#toString()

[Yaffle]

  function ilog2_bitwise(value, start) {
    var ebase = start;
    while ((value >> ebase) > 0n) {
      ebase <<= 1n;
    }
    let e = 0n;
    while (ebase >= start) {
      if ((value >> ebase) > 0n) {
        value >>= ebase;
        e += ebase;
      }
      ebase >>= 1n;
    }
    return e;
  }

  function ilog2_optim(bigint) { // supposing the best that we can do...
    let guess = Math.floor(Math.log(Number(bigint)) * Math.LOG2E + 0.5);
    if (guess < 48) {
      // it is always correct
      return guess;
    }
    if (guess < 1 / 0) {
      // small enough
      if ((bigint >> BigInt(guess)) < 1n) { // please, check it
         guess -= 1;
      }
      return guess;
    }
    //... switch to ilog2_optim with base=2n**1024n, divide, go to small
    var y = ilog2_bitwise(bigint, 1024n);
    var r = bigint >> y;
    var g = Math.floor(Math.log(Number(r)) * Math.LOG2E + 0.5);
    return Number(y) + g;
  }