JavaScript: passing by value or by reference?

Probably of no interest at all but who cares? I certainly don’t 😉

In my already regretted start to write a bigint library in JavaScript from scratch I’m porting some code from a C library (libtommath) which does a small amount of pointer juggling end reference pushing.

In the times of asm.js and tools like emscripten it could be a small command line … uhm … command but that results in a considerably large blob of nearly unreadable JavaScript code. Although a fast one.

Being fast is not that bad for a large-number library but readability wins almost always in my case.

Now I’m lost and forgot what I was to say…

Ah, the problem of pointers and passing of references and values in JavaScript. The latter is simple: Objects gets passed as references, Strings are immutable and the rest gets passed as values.

An Array is an Object, which means it can pass as a pointer replacement. My current problem (which is a very old one btw) is the fact that there is no direct way to do 32 Bit integer operations. Adding is ok, division is ok but multiplication is a pain in the part of the body most people use to sit on. So you have to do something like this which is a generalized version of the inner loop of a multiplication algorithm (D. Knuth. TAoCP v. 2 p 268, algo. M or similar)

function muluint32(a,b,r,c,B){
  var mask  = (1<<(B>>1)) -1;
  var shift = (B>>1) ;
  var bl = b & mask;
  var bh = b >>> shift;
  var al = a & mask;
  var ah = a >>> shift;
  var m = bh * al + ah * bl;

  al = bl * al +( (m & mask) << shift ) + r + c >>>0;
  c = (al >>> B ) + (m >>> shift) + bh * ah >>>0;
  r = al & (b-1) >>>0;
}

It multiplies the unsigned integers a and b of base B < 32 including carry if any (more a muladd kind of algorithm) and puts the low word of the result in r and the high word (carry) in c (the term (al >>> B ) is of course superfluous if B = 32).
This snippet does not work. But we can make it work when we replace the unusable pass-by-value variables with two arrays.

function muluint32(a,b,r,c,B){
  var mask  = (1<<(B>>1)) -1;
  var shift = (B>>1) ;
  var bl = b & mask;
  var bh = b >>> shift;
  var al = a & mask;
  var ah = a >>> shift;
  var m = bh * al + ah * bl;

  al = bl * al +( (m & mask) << shift ) + r[0] + c[0] >>>0;
  c[0] = (al >>> B ) + (m >>> shift) + bh * ah >>>0;
  r[0] = al & (b-1) >>>0;
}

Now we used two Arrays for two Numbers. That’s quite a waste, isn’t it? But I’ve talked about the Bigint project at the start of this preposterous babble I snootily call blog-post and in this case, the Arrays are the two numbers that gets multiplied. That means that a and b are elements of two Arrays A and B. If we work with these Arrays instead of the individual elements we can use the result r directly and can either return the carry c or, to make the function threadsafe, pass it as in the second example above as the element of a single element Array.
How can we make the function use the correct element of the array? We need to pass it to the function, too, right.

function muluint32(A,i_a, B,i_b, R,i_r, c, B){
  var mask  = (1<<(B>>1)) -1;
  var shift = (B>>1) ;
  var a = A[i_a], b = B[i_b];
  var bl = b & mask;
  var bh = b >>> shift;
  var al = a & mask;
  var ah = a >>> shift;
  var m = bh * al + ah * bl;

  al = bl * al +( (m & mask) << shift ) + R[i_r - 1] + c[0] >>>0;
  c[0] = (al >>> B ) + (m >>> shift) + bh * ah >>>0;
  R[i_r] = al & (b-1) >>>0;
}

This is quite slow in native JavaScript but asm.js is not a good alternative because of the restrictive memory management: you get to reserve one amount and that was it. So I decided to use 26 bit long big-digits. One caveat still: The bit-operations in ECMAScript are restricted to 32-bit, so something like the following will fail

r_52_bit = a_26_bit * b_26_bit;
...
carry = r_52_bit >>> 26;

You need to use division by the base (here 1<<26 = 0x4000000) instead:

r_52_bit = a_26_bit * b_26_bit;
...
carry = Math.floor(r_52_bit/0x4000000);

That won’t make it faster but the alternative with bit-juggling is even slower.