Monthly Archives: September 2014

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. Continue reading

Adventures of a Programmer: Parser Writing Peril XXXVII

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[0]);
console.log(a.negate()[0])

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.

Great.

An I thought I could do the whole thing in two or three month.

Silly me! πŸ˜‰

Global Variables in JavaScript

Global variables are an absolute no-go.
End of post?
No, of course not. But there is one nagging detail in ECMAScript that allows for so called implied global variables. You can get them quite easily, just forget to add a declaration var ident; and you have one. JavaScript knows now real variable scope, only inside and outside a function so it assumes it was a global variable (his might not be the case with every browser and other engine but it was in older ones, so YMMV) even if it is just a misspelling of a local variable. That can lead to some very interesting debugging sessions if the lines of code are legion and carefully spaghettified.
I don’t think there is a solution for it. You can try JSlint but it is a it behind, closed-source (or I just couldn’t find it) online, so one does not know what happens to your data.

But that rant was just a digress, not what I wanted to talk about.

ECMAScript is single threaded, global variables are a very small problem in such an environment, but you can have so called Web-Workers a very limited form of threads introduced in the HTML5 standard. With multi-core CPUs so common, even in cell-phones it starts to make sense. This ignores the fact that the JavaScript engine must translate the web workers into something that is not only threadable but supports multi-cores,too.

Now, global variables are a real problem. Webworker are a very primitive form of threads, as mentioned above, so none of the useful things from e.g.: the Posix threads exist. You can start it, end it, send messages to it and let it send messages to you. You can only send one Object as it seems but that is enough as you can use JSON or equivalent to tie up a parcel, pardon Object. This packet seems to get passed as a full copy, so be aware of memory restrictions. Which limits you can’t find within JavaScript btw. But if the packets are small and the processing is not only heavy but also parallelizable (say that ten times fast πŸ˜‰ ) it makes sense to use web-workers.

Now what to do with global variables; how to get and more so how to set them concurrently?

The Posix threads have a couple of quite nasty but very useful things to handle that, Web-Workers don’t. The don’t know anything about shared memory, they just don’t have shared memory. Webworkers are just some glorified processes.

If you need only small amounts of shared memory, say up to 2.5 MB than you can make use of some of the small external storages the new ECMAScript offers, for example localStorage, although it can only save strings.

log(gamma) Function in JavaScript over the Real Line

I took the Stirling mechanism from the lngamma function we talked about in our last post and made it work over the real line. Works smooth and with a good accuracy of at least 14 decimal digits (in the more usual cases 15 or even the full 16) over the whole range a 64-bit double allows.
It is slower, of course, which is obviously caused by the dynamical evaluation of the number of needed Stirling terms.
But I can put in places where the other log-gamma function has its weaknesses, for example near one and two.
Or I can pre-calculate the number of terms (for the native JavaScript numbers at least) for some ranges of input and implement just these ranges.
Putting both of the paragraphs above together might be a good idea.

What’s all the fuss about? one might ask but a good, stable and fast lngamma function is used in so many places, it is worth all of the hassle.

If somebody is interested in the code go to…uh, forget it, I put it under the fold πŸ˜‰ Continue reading

Adventures of a Programmer: Parser Writing Peril XXXVI

The Logarithm of the Gamma Function over the Complex Plane with a Smooth Principal Value

As an approximation of course (where applicable) done with the Stirling series but that information would have made the header a wee bit too long.

The problem with the Stirling series is that the number of summands depend on the input; there is an ideal number of summands for a given precision. But don’t worry, D.E.G. Hare did all the math for us. Continue reading

Adventures of a Programmer: Parser Writing Peril XXXV

Added some basic function and needful utils to the library of Little. Most of it from my old pragmath package. Of larger interest might be a port of GNU-coreutils’ factor and a port of Boost’s Gamma functions for real arguments. I wanted to base the gamma functions for complex arguments on these but they are lacking too much of accuracy for some arguments (near one and two), mainly in the log-gamma function.

I forgot if I already wrote about it and am too lazy to look it up (as if I have written thousands of posts πŸ˜‰ ): the problem is the principal value of the \log\Gamma() function which is different from \log\left(\Gamma\left(\right)\right) on the left complex half-plane except the real-line which can be ignored because of \Re\left(\log\Gamma\left(\right)\right) =  \log\left(|\Gamma\left(\right)|\right) [1]:

\Im\left(\log\Gamma\left(\right)\right) = \Im\left( \log\left(\Gamma\left(\right)\right) \right) + 2k\left(x\right)\pi = \begin{cases} 2k\left(x\right)\pi & \text{if } \lfloor x\rfloor \text{ is even}\\ \left(2k\left(x\right)\right)\pi & \text{if } \lfloor x\rfloor \text{ is odd} \end{cases}

Now what is the function k you might ask. Well, it is in the paper πŸ˜‰
But I have done not only the long-winded arbitrary precision function implemented in calc but also a small, readable version for testing purposes. Please look under the fold. Continue reading

Adventures of a Programmer: Parser Writing Peril XXXIV

Overloading

We have mainly two different numbers in Little: the real numbers and the complex numbers. The latter are actually the imaginary part only but that changes only very little on the programming side and nothing algorithmically.

We want to treat them both the same syntactically, so 3 * 2 + 4i must be possible and a + sqrt(b) must not give an error, no matter what the content of b is. Continue reading