Adventures of a Programmer: Parser Writing Peril XXXIV


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.

The internal work gets complicated by the fact that we want to do arbitrary precision, which increments the number of numbers even further: Bigint, Bigfloat and probably Bigrational, too. A rational data type is not only useful for exact (but very slow ) computations but also for the evaluation of some constants, for example the Bernoulli numbers.

In our program arbitrary precision is not really arbitrary precision but multiple precision because we cannot adapt the precision dynamically we have to set it in advance. If you have to calculate the Bernoulli numbers every time the precision changes you cannot make a lot of use of caching. If you keep them as rationals on the other hand, they are independent of the current precision.

No good deed gets unpunished which is the case here, too: to get decimal representations you need to actually divide the fractions. You can cache the results but it is still a quite expensive division. For single values of higher orders of Bernoulli numbers another algorithm gets used involving the Riemann-zeta function where half of the calculation is already decimal but high orders really means high orders much larger than B_{1\,000} \approx -5.3187 \times 10^{1769}. The denominator of B_{1\,000} by the way is quite small, only 342999030 and if you go one step further you’ll find the denominator of B_{1\,002} to be 42. Another funny fact is that the denominator of B_{10\,002} is also 42.

But back to the main theme:
The way I solved it is to keep the two main number-types: real and complex with the latter an abstract type holding two of the other number-types for the real and the imaginary part respectively, either Big* or Number with both, the real and the imaginary part being independent. You can have a Number real part and a Bigrational imaginary part for example but no nested values, e.g.: no Complex imaginary part to keep it simple.

We can implement this in roughly two different ways: the faster but complicated and the slower but simple way. According to our premise we always chose the simple way (first). The simplest way is to take what is already written, of course 😉
I implemented such thing a longer time ago, so we are going to use it. Probably
The main idea is to write the a function name foo (eg.: add) doing operation foo (e.g.: addition) for every data-type and “go up” if necessary. Example:
The Complex data type is quite simple because it is only an abstract type, a mere container.

function Complex(a,b){
  this.Re = (arguments.length > 0) ? a : 0 ;
  this.Im = (arguments.length > 1) ? b : 0 ;

The mathematical operation addition for complex numbers does not rely on the data-type,we can add all our data-types, be it Complex, Big*, Matrix, Quaternion, or Poly.

Complex.prototype.add = function(i){
  var a = this.Re;
  var b = this.Im;
  var c;
  var d;

  var ret = new Complex();

  if(xtypeof(i) != "complex"){
    i = i.toComplex();
  c = i.Re;
  d = i.Im;

  ret.Re = a.add(c);
  ret.Im = b.add(d);

  return ret;

Every data-type has the prototype toComplex but it does little safe some checks for anything except strings which needs to get parsed.
Th algorithm of addition of two complex numbers is to add the real and imaginary parts respectively. Addition is addition no matter which data-type so every data-type has a prototype’d function named add. Main disadvantage is that the data-type Number needs one, too. Simplified:

Number.prototype.add = function(i){
  if(typeof i === "number"){
    return this + i;
  else if(i instanceof Complex){
    return this.toComplex().add(i);
  /* and so on */
  else return Number.NaN;

A lot of overhead for a simple addition but it is not that slow. This code was written and run on an old Pentium 200. No, not 2GHz, 200MHz! With the gigantic amount of 32 MB RAM. No, not giga-bytes, mega-bytes! And it run ok. Won’t break world records, but it’s ok.

The best real world example to show actual use of the system is probably the square root:

Number.prototype.sqrt = function(){
  if(this > 0)
    return Math.sqrt(this);
    return this.toComplex().sqrt();

My old code needs some clean-up but I’ll upload a basic version (Complex and Number only) to the libs directory of Little tomorrow. Or maybe even tonight if there isn’t much to change which is unlikely, I know myself 😉


Leave a Reply

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

You are commenting using your 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