Now that I had some time at hand, even though it is Sunday, I laid my hand on Tom Wu’s big integer library to smooth out the edges, test my implementations of Karatsuba and Toom-Cook algorithms and other bits and bobs. A bit boring but there is a need to do so and that is not only my own opinion. It just suffers from a lot of old-browser-legacy. That is a thing I know very well and hate even more than seeds in my raspberry jam.
The thing I wondered about was the line
Bigint.ZERO.subTo(this,r) to negate a bigint. It does exactly what you think it does, it subtracts a number from zero. So it is easily replaced by just changing the sign, isn’t it? Nope, of course not. The variable
bigint.s is just a shortcut, you wouldn’t need it, the respective digits are negative, too. Try it out:
var a = nbv(-923); console.log(a); console.log(a.negate())
will result in 268434533 (0xffffc65) and 923 (0x39b) respectively. Padding to the left with ones and bit-negating the first result gives ~0xfffffc65 = 922.
I will not go to the length and explain the reason for this, just say that this made some things simpler algorithmically but a lot of it is also caused by the (mis)behaviour of old browsers. A hint: if you look at the start of his file you’ll find the name “Netscape” at one point. The younger ones of you might even need to ask Google what it was.
The last version had been published in February 2008 but the last version that was used in large numbers was probably 4.76 published in October 2000. My old SparcStation runs an older version of OpenBSD and I installed Netscape 4.76 as the browser 😉
So, at the end of this song I will have to bite the bullet, grab Tom St Denis’ paper and rewrite it from scratch.
An I thought I could do the whole thing in two or three month.
Silly me! 😉