Inequalities Visualiser

This project was made as part of my design project module. The design project module is one of the two graduation modules for the bachelor in technical computer science at the University of Twente. I have worked on this project together with Neil Kichler, Max Resing and Rifqi Adlan Apriyadi. Most of the project is written in c++. The git for this project cannot be shared.

Abstract

The nature of mathematics is to provide precise answers and conclusions to a given problem. Whereas in practice, precision is a variable term and should rather be seen as accuracy. A temperature sensor can indicate that the temperature is 21 degree Celsius. But this measurement is actually an approximation and depending on the accuracy of the sensor, the actual temperature lies within an interval of 20.5 to 21.5 degree Celsius.

This is essentially where interval arithmetic excels. Interval arithmetic is a mathematical technique to provide precise answers in a domain of uncertainty. In general, interval arithmetic provides the same arithmetic, trigonometric, numeric and Boolean operations which other fields of mathematics use. Nonetheless, interval arithmetic has some special rules and characteristics which may seem unconventional.

The product we are working on is build on top of the theory of interval arithmetic. Since interval arithmetic supports the regular common operations like addition, subtractions, multiplication and non-negative exponentiation, one can also build polynomials in interval arithmetic. These polynomials can be added to an inequality. An inequality is essentially a polynomial compared to a Boolean operation. The polynomial can have arbitrarily many variables. In an inequality, one can try to assign intervals to each variable. Next, one can try to shrink the intervals of each variable to draw conclusions under which set of numbers a given inequality holds true or false. The process of reducing the size of the intervals is called refinement.

Our application is a tool which visually supports the user to refine a given inequality and to draw conclusions about the inequality statement. The software helps to understand the characteristics of interval arithmetic. Furthermore, it supports a user's thinking process when working with intervals and inequalities.

Showcase

My Contributions

Parser: For this project I took the responsibility of building a parser for polynomials with support for intervals. At first, we thought that this was not necessary as we figured that such a parser would already exist. Although such a parser does exist, it turned out that none of the parsers would return a structure from which we can create our internal structure which should support interval arithmetic. And so it followed that I had to make a new parser from scratch in c++. Because of the experience I have in writing a parser because of the 'PyVa' project, it turned out not to be that bad to write it from scratch. Many of the concepts from ANTLR were re-used to build the parser. The result contained a Scanner, Tokenizer, Grammar with Terminals and Non-terminals, Abstract Syntax Tree with ParseTreeProperties, an abstract ASTVisitor and an InEqualityWalker which extends from the ASTVisitor. Although the exact implementation could be interesting, it is too large to show (211 lines just to create all parser rules and link them together). So instead, a grammar is given in ANTLR style below.

        
Goal                : TernarySequence
TernarySequence     : Evaluable TernarySequence'
TernarySequence'    : TernaryOperation Evaluable TernarySequence' | epsilon
TernaryOperation    : '&' | '|'
Evaluable           : InEquality | '(' TernarySequence ')'
InEquality          : '(' Expression EqualityOperation Expression ')'
InEquality          | Expression EqualityOperation Expression
Expression          : Term Expression'
Expression'         : OperatorAdd Term Expression' | epsilon
OperatorAdd         : '+' | '-'
OperatorMult        : '*' | '/'
Term                : Exponent Term'
Term'               : OperatorMult Exponent Term' | ImplicitTerm | epsilon
ImplicitTerm        : PExponent Term'
Exponent            : NFactor Exponent'
Exponent'           : 'ˆ' NFactor Exponent' | epsilon
PExponent           : Factor Exponent'
Function            : FuncName '(' Expression ')'
FuncName            : 'sin' | 'arcSin' | 'cos' | 'arcCos' | 'tan' | 'arcTan' | 'sqrt' | 'log' | 'ln'
Factor              : Numeric | Function | Variable | '(' Expression ')'
NFactor             : '-' Factor
Variable            : [a-zA-Z]
Numeric             : Float | Number
Number              : [1-9][0-9]*
Float               : Number '.' Number
        
    

Because the goal of the project was to support polynomials, it was desired that you could input these polynomials in the same way you would write them down on a sheet of paper. This meant that the parser had to support implicit multiplication. In other words, you should be able to express, for example, a second order polynomial like this: 'ax^2 + bx + c'. This feature is supported by the rule ImplicitTerm. This does look a bit odd if you start combining implicit multiplication with function calls. For example, you could do 'sincos(0.5)s' which would internally be represented as 's * i * n * cos(0.5) * s', where the single characters are considered variables.

Expression EDSL: In order to support evaluation of polynomials, we needed to create our own polynomial expression (or polynomial) EDSL. This EDSL defines the internal representation of the polynomials. Since a user may request to calculate thousands of intervals at a time, the EDSL has been made stateless such that we can evaluate the result for multiple intervals simultaneously.

Evaluating trigonometric functions with intervals: Trigonometric functions are non-monotonic. This means that these functions are not entirely increasing/decreasing. This is an important distinction to make with interval arithmetic. Consider any monotonically increasing function i, any monotonically decreasing function d and any non-monotonic function n. For all intervals in the real number space [x, y]: i([x, y]) = [i(x), i(y)] and d([x, y]) = [d(y), d(x)] is always true but n([x, y]) = [n(x), n(y)] or [n(y), n(x)] is not always true as the interval may cause the function to wrap around a peak. For example sin(-2π, 2π) ≠ [sin(-2π), sin(2π)] as this would yield the interval [0, 0] whereas it should have been equal to [-1, 1].