GitHub - kclapper/tower.js: Javascript implementation of Scheme’s numeric tower

Javascript implementation of Scheme’s numeric tower - kclapper/tower.js

GitHubkclapper

I was a PhD student for about a year before I realized it wasn't for me and switched to the master's program. I studied programming languages and as part of the Racket community working on Racketscript. Racketscript is a Racket to Javascript transpiler and it's still under active development. At the time, Racketscript didn't support complex or exact numbers.

Racket, unlike many programming languages, has complex numbers as a language primitive. You can do complex math with the algebraic operators and get complex numbers as a result. Racket has the concept (inherited from Scheme) of the numeric tower.

All numbers are complex numbers, a subset of those are real numbers, a subset of those are rational, and a subset of those are integers. There is another concept orthogonal to the numeric tower called exactness. All numbers can either be exact or inexact. Exact numbers are represented as an integer numerator and denominator. There are no rounding or truncation errors when you do math with exact numbers. Inexact numbers are represented as floating point numbers and behave as you'd expect.

While a number system like this increases the language and implementation complexity, there are two big benefits (in my opinion):

1. You can do math with exact numbers to avoid rounding and truncation issues. This is of particular importance in some science and engineering disciplines like aerospace engineering or astronomy.
2. You can easily do math with complex numbers and with better performance than a library implementation. This is important in domains such as digital signal processing.

js-numbers

Racketscript didn't have support for complex or exact numbers so I set out to build it. There was an existing 10 year old library called js-numbers that implemented the scheme numeric tower in Javascript. It wasn't originally intended for Racketscript, but since Racket is a descendant of Scheme it served as a good starting place, so I forked it on GitHub.

js-numbers appears to predate npm and modern Javascript tooling. For example, it used an old Java library for bundling the source code. I decided I would rewrite it as an npm package using Typescript. By making it an npm package, anyone else who needed an implementation of the Racket numeric tower could use it too.

The second benefit to doing a rewrite was that I could add modern Javascript language features, namely bigints. Bigints give Javascript programmers an arbitrarily large integer type. Normal Javascript numbers have a maximum and a minimum safe integer value. This is because all numbers in Javascript (other than bigints) are represented as floating point numbers. Meaning once the number becomes too big to fit in the significand, it starts being rounded in order to fit. Bigints end up making it easier to represent exact numbers because you don't have to account for the minimum and maximum safe integer values.

The Implementation

For the rewrite, I renamed the library tower.js. Like I mentioned above, it's written in Typescript and uses modern Javascript tooling like npm and Webpack. Since Scheme is a functional language, the API of js-numbers was functional as well. Users of the library would do math by calling functions like:

var three = add(1, 2);
var fifteen = multiply(three, 5);

I thought this API was fitting so I kept it and added some missing Racket functions. I tried to mimic the Racket functions as best as I could in tower.js.

While the API is functional, the number representation is object oriented. I use classes to represent the boxed versions of numbers. To optimize performance, some number types can be represented as unboxed Javascript primitives. For example, exact integers can be represented directly as bigints and inexact real numbers can be directly represented as normal Javascript numbers. These unboxed numbers can use the builtin Javascript arithmetic operators which are must faster than calling class methods.

This dual representation, boxed and unboxed numbers, made the implementation of the API functions more complex. In each function, there needs to be a check to see if a number is boxed and should be unboxed or vice versa. This boxing/unboxing behavior can end up hurting performance depending on what computations are being performed.

The Results

Exact complex, expt(100+89i, 5000)
--------------------------------------------------------------------------
js-numbers: 7.4032 ms/trial (740.3240 total)
tower.js: 	0.3210 ms/trial (32.1035 total)
Results match: true

Large Exact integer, expt(1000, 5000)
--------------------------------------------------------------------------
js-numbers: 5.4490 ms/trial (544.9012 total)
tower.js: 	0.0984 ms/trial (9.8447 total)
Results match: true

Small Exact Base and Exp, expt(2, 30)
--------------------------------------------------------------------------
js-numbers: 0.0003 ms/trial (0.0389 total)
tower.js: 	0.0008 ms/trial (0.0809 total)
javascript: 0.0002 ms/trial (0.0277 total)
Results match: true

Small Inexact Base and Exp, expt(5.5, 5.5)
--------------------------------------------------------------------------
js-numbers: 0.0019 ms/trial (0.1926 total)
tower.js: 	0.0006 ms/trial (0.0638 total)
javascript: 0.0002 ms/trial (0.0283 total)
Results match: true

Mixed Precision, expt(5.5, 10)
--------------------------------------------------------------------------
js-numbers: 0.0006 ms/trial (0.0683 total)
tower.js: 	0.0006 ms/trial (0.0602 total)
javascript: 0.0002 ms/trial (0.0279 total)
Results match: true

I did some micro-benchmarks to try and assess the performance impact of the rewrite. The rewrite ends up benefiting from using bigints to represent exact numbers. The js-numbers library had to implement exact numbers using Javascript numbers and library functions. Bigints, on the other hand, have native runtime support which makes them much faster.

The bench-marking results above don't show it, but in typical use cases the rewrite is as fast or slower than js-numbers. Where it beats out js-numbers is when it comes to exact numbers due to its use of bigints. Bigints allow for more unboxed operations which are significantly faster.

Tower.js also supports more functions than the original js-numbers library did. In particular, it implements the bitwise functions, which are needed to build a Racket runtime in Javascript. Since it was written in Typescript, it also comes with typings that could help library users distinguish between native Javascript numbers and the various tower.js number types (and also help them write type-safe code).

If you want to check out tower.js you can find it on GitHub. You can also find documentation on the GitHub Pages site.