DDMathParser

Today’s blog entry (and hopefully for a few more) is about Dave DeLong’s DDMathParser, which is hosted here:  https://github.com/davedelong/DDMathParser.

I found DDMathParser after I wrote a calculator app that was intended to provide very precise math, when I was looking to improve its parsing of equations.

I’m also a little obsessed with numeric precision, but only a smidgen.

Computers and programmers usually represent “real number” types using float or double in C/C++ (and similarly-named types in many other languages). These can store a certain number of digits and an exponent. If you exceed that number of digits, you are no longer doing math precisely, and that can be VERY important when you dealing with money.

Never use float or double to calculate quantities of money that are large or which need to be precise. (Who likes sloppy accounting?)

To illustrate the lack of precision that double gets you, we can run the command-line demo of DDMathParser:

Math Evaluator!
    Type a mathematical expression to evaluate it.
    Type "functions" to show available functions
    Type "operators" to show available operators
    Type "exit" to quit
> 300.1 ** 14
    Parsed: pow(300.1,14)
    Rewritten as: 4.805337947671661e+34
    Evaluated: 4.805337947671661e+34
> 300.1 ** 14 + 1
    Parsed: add(pow(300.1,14),1)
    Rewritten as: 4.805337947671661e+34
    Evaluated: 4.805337947671661e+34

As you can see here, (300.1 ** 14) prints out as 4.805337947671661e+34,
and (300.1 ** 14 + 1) prints out as              4.805337947671661e+34.

(I’ve made sure the two numbers line up so you can see that they look the same.)

They not only look the same, but when I use == to compare them, it says they are the same!

> 300.1 ** 14 == 300.1 ** 14 + 1
    Parsed: l_eq(pow(300.1,14),add(pow(300.1,14),1))
    Rewritten as: 1
    Evaluated: 1

However, Dave provides a “high precision” option. So let’s turn that on.

In main.c we have:

int main (int argc, const char * argv[]) {
    ...
    DDMathEvaluator *evaluator = [[DDMathEvaluator alloc] init];

and when we look at the header file DDMathEvaluator.h we see:

    @interface DDMathEvaluator : NSObject

    @property (nonatomic) BOOL usesHighPrecisionEvaluation; // default is NO

so let’s add a line to main.c:

int main (int argc, const char * argv[]) {
    ...
    DDMathEvaluator *evaluator = [[DDMathEvaluator alloc] init];
    [evaluator setUsesHighPrecisionEvaluation: YES];

and run the command-line demo:

> 300.1 ** 14
    Parsed: pow(300.1,14)
    Rewritten as: 48053379476716554740761909736735670.908
    Evaluated: 48053379476716554740761909736735670.908
> 300.1 ** 14 + 1
    Parsed: add(pow(300.1,14),1)
    Rewritten as: 48053379476716554740761909736735671.908
    Evaluated: 48053379476716554740761909736735671.908
> 300.1 ** 14 == 1 + 300.1 ** 14
    Parsed: l_eq(pow(300.1,14),add(1,pow(300.1,14)))
    Rewritten as: 0
    Evaluated: 0

This time, instead of (300.1 ** 14) printing out as 4.805337947671661e+34,
it prints out as 48053379476716554740761909736735670.908; and, (300.1 ** 14 + 1)
prints as        48053379476716554740761909736735671.908.

In default precision mode, DDMathParser uses NSNumber, which uses float in 32-bit applications, and double in 64-bit apps. (The Swift version currently uses Double instead of NSNumber and doesn’t implement a high precision mode.)

In high precision mode, DDMathParser uses NSDecimal. Apple has provided NSDecimal as a money-safe numeric type in Foundation/NSDecimal.h.

NSDecimal can represent some big numbers very precisely, but it has a limit on the magnitude and number of digits it allows. According to Apple’s documentation for NSDecimalNumber (which seems to use NSDecimal internally), NSDecimal can represent any number that can be expressed as (mantissa * 10 ** exponent) where mantissa is a decimal integer up to 38 digits long, and exponent is an integer from –128 through 127.

We can test these limits using factorial:

> 103!
    Parsed: factorial(103)
    Rewritten as: 9902 9007164861 8040754671 5254581773 3488000000 
                       0000000000 0000000000 0000000000 0000000000 
                       0000000000 0000000000 0000000000 0000000000 
                       0000000000 0000000000 0000000000 0000000000
    Evaluated: ...
> 104!
    Parsed: factorial(104)
    Rewritten as: NaN
    Evaluated: NaN

(I modified the output to group digits by tens.)

I picked factorial because DDMathParser’s code to compute factorial with NSDecimal explicitly looks for the error NSCalculationOverflow. I found only four other places checking for underflow/overflow/etc., so I conjecture that most math in DDMathParser isn’t checking for those kinds of errors. (I could be wrong.)

In comparison, Python has infinite-precision integers, making it very good for financial calculations. Check it out:

$ python
Python 2.7.10 (default, Jul 14 2015, 19:46:27) 
[GCC 4.2.1 Compatible Apple LLVM 6.0 (clang-600.0.39)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> import math
>>> math.factorial(103)

   9902 9007164861 8040754671 5254581773 3490901658 
        2211449248 3005280554 6998766658 4162228321 
        4144107388 3538492653 5163859772 9209322288 
        2134415149 8915840000 0000000000 0000000000L

>>> math.factorial(104)

1029901 6745145627 6238485838 6476504428 3053772454 
        9990721823 2549177688 7871732475 2871745427 
        0987168388 8003235965 7041416383 7769517974 
        1979175588 7247360000 0000000000 0000000000L

(I also modified this output to group digits by tens.) Notice that the DDMathParser/NSDecimal version of 103! isn’t the same as Python’s 103!.

There’s a lot to explore with DDMathParser. For one, how does it actually parse out equations? For two, can we convert it to Swift? For three, what might be different if we developed this code in a test-driven style?

Dave has already converted some (most?) of the DDMathParser code to Swift. I’d like to get some practice with Swift, so in the next blog entry of this series, I’ll try to write some unit tests for some DDMathParser classes.

Other ideas: If we add overloaded math operators for NSDecimalNumber, we can simplify how that class can be used. If we wrap NSDecimal or NSDecimalNumber in a Swift struct, that might be even better. Swiftifying NSDecimal or NSDecimalNumber could be a separate project, but since it’s a good practice to actually use the code that you write, I’d like to do that in the context of DDMathParser.