A new old calculator in town

2014.03.06

This article expresses the author's opinion at the time of writing. There are no guarantees of correctness, originality or current relevance. Copying the whole article is forbidden. Transcription of selected parts is allowed provided that author and this source are mentioned.

After more than one year of work, a new scientific calculator is born: the HP-15C emulator. It is available for the Web and Android, and more ports are coming. The source code is available at GitHub.

At first glance, the 15C looks like a 11C with just a couple more functions. Certainly it shares the form factor and the RPN stack mechanics. But the 15C has many additional, and powerful, features: matrix operations, complex numbers, equation solving and numerical integration.

In terms of lines of code, the 15C implementation is almost twice as big as 11C. The 15C-specific features add up to code size because they need to be implemented from scratch, more like 16C binary operations, and no help from Javascript standard modules.

I could have adopted third-party libraries. At least for matrixes, there are many good libraries for Javascript (certainly inspired by the rise of WebGL). I chose to implement everything myself, due to the following reasons:

- Because it is fun :)
- Seemed to be a good opportunity to refresh my memory on math topics like linear algebra, complex numbers, etc.
- The source code makes a good one-stop documentation on the topics.
- In some corner cases, HP-15C does things in its own way. For example, it can invert singular matrixes by "tweaking" the values a bit.
- Third-party dependencies imply to track their future developments, in case bugs arise. Licenses must also be taken into account, etc.

I am aware of the downsides. It is possible that Sylvester.js has better numerical stability than my implementation.

A big exception in this NIH policy of mine is the
random number generator.
It had already been adopted in 11C emulator, since Javascript's random() cannot
be seeded.
*UPDATE: I found that 11C and 15C uses an LCG PRNG, which is very easy to
implement. Currently the emulator uses this type of PRNG, and this library
dependency has been removed.
*

About the "documentation" character of the source code, one would expect that such basic mathematical algorithms are readily available in the Internet. Indeed there is a lot of information online, but it is scattered and incomplete.

One example is LU decomposition, a matrix algorithm.
I found it "ready" at the Internet, but it took a lot of
work to be usable.
I even wrote a separate
article about it, so *now* I can say it is perfectly documented :)
The same happened for numeric integration and root-finding algorithms.

Still, having online sources was better than having no information at all. URLs of most useful references can be found as comments in the code.

Among the advanced features of 15C, complex number support was the easiest to implement. My life would be easier if Javascript had native support to complex arithmetic, as Python does. At least I could count on Python to do many cross-checks and unit tests.

Apart from LU decomposition, matrix handling was straightforward to implement.
The big problem was to make sure that the implementation is ok. Again, Python
came to rescue; *numpy* and *scipy* together implement all typical
matrix operations. I ended up writing a "unit test generator" in Python because
of the sheer number of test cases to cover.

Having mentioned unit tests, current code coverage is no less than 100%, for all calculators (12C, 11C, 16C and 15C). I had been satisified with ~90% coverage for a long time, but since the 15C was completely new and untested, 100% coverage was necessary to have any degree of trust in this new code.

100% coverage forces the unit tests to simulate all corner cases and error conditions, and I must say I found many, many bugs (most of them minor, thankfully) hidden in exceptional handling. Another thing I found is a lot of unreachable code, e.g. for errors that can't happen at all. You need to think every case over, and decide if removal of code is the way to go.

Numeric integration uses the Adaptive Simpson algorithm. I found that the algorithm in the respective Wikipedia article was nearly usable "as is". The detail that took additional work was the desired precision — the user can select the precision by displaying more or less decimal places. 3 decimal places yields an integration exact in the first 3 significant digits.

Unit testing of numeric integration was not difficult at all, because there are many well-known functions to choose from. For example, integrating 1/x from 1 to n is equal to ln(n). It looks simple but it is a challenge to integrate with good precision. The 1/x curve was of great help to tune the implementation.

Equation solving (i.e. finding its roots) was certainly the most difficult feature to implement and test properly. It uses a handful of algorithms. The HP-15C has a reputation of finding roots even in face of "difficult" functions, and our calculator endeavors to match or surpass the 15C in this area.

Given some equation y=f(x), the calculator wants to find a root *r* that makes f(r)=0.
The basic strategy is to find *a* and *b* that makes f(a)>0 and f(b)<0.
Once *a* and *b* are found, the root is easily found.
The difficult part is to find this range *a..b* that contains the root.

Our implementation uses two basic methods: secant and Muller's. The secant method has additional heuristics that detect e.g. exponential and sub-linear functions. The secant method is expected to fail with U-shaped functions (parabolas), so the Muller's method is given a try when the secant method fails to contain the root.

Another implementation challenge imposed by equation solving, and also by numeric integration, is the "context switching" between the solving algorithm and the running program. In the HP-15C, the function to be solved is expressed as a program subroutine. The algorithms need to run this subroutine many times to get sample values and solve the equation.

Due to this, the root-solving algorithm needs to yield control while the program runs.
It is structured like a generator. I did
not use Javascript's *yield,* fearing it is still not supported by all browsers,
but I missed it a lot in this case.

Another complication is the possibility of having SOLVE and/or INTG in a program. Or SOLVEing a function that uses INTG, or INTGrating a function that uses SOLVE. The real HP-15C allows either combination, it just forbids recursion (e.g. integrating a function that uses INTG itself).

To cope with that, we implemented a stack of running contexts. When e.g. a program invokes INTG, a new context is created. When the INTG subroutine terminates, its context is popped and the program's context is resumed. In case of error, the whole context stack is unrolled, causing the top-level program to stop.

I did not implement "apocryphal" features (i.e. features not present in a real HP-15C). I had put enough effort on it already, and the public release couldn't wait forever. But I still plan to do it one day. For example, matrix exponential is not supported by HP-15C, an omission that is a bit surprising. There are many other mathematical operations that currently don't support matrixes and could be augmented in that direction.