Adventures of a Programmer: Parser Writing Peril XXXX

The final[1] grammar together with the lexer. The whole file with a lot of comments is on Github. It is currently in one file for convenience but needs to be split into a lexer (Flex) and a parser (Bison) later.

The file has a lot of comments already, not much to say here, but nevertheless… 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! 😉

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

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