Javascript: Number (double) to Bigint

Now that my Bigint library is slowly working (you cannot test it before you have implemented the most basic functions, that is, almost all) I can start to implement the needful little things that will make working with that monster a wee bit less unpleasant.

One of the things one might use more often ist the cast of a JavaScript Number to a Bigint. It is quite easy if it is a small integer fitting into the 53 bit limit, it is not so easy if it doesn’t.
The code for the case when it fits:

// returns Bigint. Bigint might be set to Nan or Infinity if Number is
// not a small enough integer. Range: -9007199254740992..9007199254740992
Number.prototype.toBigint = function(){
  var ret = new Bigint(0);
  // Check Number
  if(!this.isOk() || !this.isInt()){
    ret.setNaN();
    return ret;
  }
  // Check if Number is integer and smaller than MP_DIGIT_MAX for direct use
  if(this.issmallenough()){
    ret.dp[0] = Math.abs(this);
    ret.sign = (this < 0 )?MP_NEG:MP_ZPOS;
    return ret;
  }
  var temp = Math.abs(this);
  var sign = (this < 0 )?MP_NEG:MP_ZPOS;

  ret.dp[0] =  this & MP_MASK;
  ret.dp[1] = Math.floor(this/MP_DIGIT_MAX)&MP_MASK;
  ret.used = 2;

  ret.clamp();
  return ret;
};

The case when it doesn’t is normaly solved with some bit-pushing, here translated to JavaScript.
The functions frexp and ldexp are needed for the code below to function properly.

Number.prototype.doubleToBigint = function(){
    var fraction_part;
    var digits, int_part, exponent_part, sign, ret_frexp, t;
    var ret;

    sign = MP_ZPOS;
    t = this;
    if (!this.Ok()) {
	ret = new Bigint(0);
	ret.dp[0] = this;
	return ret;
    }
    if (t < 0) {
	sign = MP_NEG;
	t = -t;
    }
    ret_frexp = frexp(t);
    fraction_part = ret_frexp[0];
    exponent_part = ret_frexp[1];
    // rounds down to zero for 0<n<1
    if (exponent_part <= 0) {
	return (new Bigint(0));
    }
    ret = new Bigint(0);
    digits = Math.floor((exponent_part - 1) / MP_DIGIT + 1);
    ret.dp = new Array(digits);
    fraction_part =
	ldexp(fraction_part, (exponent_part - 1) % MP_DIGIT + 1);
    while (digits--) {
	int_part = Math.floor(fraction_part);
	ret.dp[digits] = int_part >>> 0;
	fraction_part = fraction_part - int_part;
	fraction_part = ldexp(fraction_part, MP_DIGIT);
    }
    ret.clamp();
    ret.sign = sign;
    return ret;
};

The main problem with this code is the infamous rounding error, creeping into every discussion about floating point numbers.
If you take a number that is below the size of the precision (<=2^53 for an 8 byte double) you get precise answers:

900719e10 = 9007190000000000

But if you get above that limit it starts to get inexact:

123.321e23 = 12332099999999999353028608 (+646971392)

Which is exactly what is in the Number: 0.637\,554\,627\,004\,074\,5 \times 2^84 = 12332099999999999353028608. If you print it you’ll get the expected value: var a = 123.321e23;a.toExponential(); will print 1.23321e+25, the internals will round the number correctly, so we can use that and if you think that is headache inducing ask Google for some examples of dtoa.c 😉
Rough sketch:

function cheap_dtoa(x){
   var ax, man,expo,ten15,tenm16;
   var ret;
   /* checks and balances ommitted */
   ax = x.toExponential().split('e');
   man = ax[0];
   expo = ax[1];
   /* checks and balances ommitted */ 
   man = man * Math.pow(10,15);
   // man < 2^52
   ret = man.toBigint();
   
   // multiply the result with 10^(exp-16)
   tenm16 = expo - 16;
   if(tenm16 == 0){
     return ret;
   }
   if(tenm16 < 0){
     return ret.div(Math.pow(10,tenm16).toBigint());
   }
   // 10^15 < 2^53
   if(tenm16 <= 15){
     return ret.mul(Math.pow(10,tenm16).toBigint());
   }
   // exponent can be large but not that large so multiply in chunks of 10^15
   ten15 = Math.pow(10,15).toBigint();
   while(tenm16-15 >= 15){
     ret = ret.mul(ten15);
     tenm16 -= 15;
   }
   if(tenm16){
     return ret.mul(Math.pow(10,tenm16).toBigint());
   }
   return ret;
}

That is computationally very expensive and I don’t like it.
But I don’t know, maybe later?

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s