{'fraction_non_alphanumeric': 0.031019124967251767, 'fraction_numerical': 0.009326696358396646, 'mean_word_length': 4.697313432835821, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Moore: Interval Arithmetic in C++20

This article presents the Moore library for interval arithmetic in C++20. It gives examples of how the library can be used, and explains the basic principles underlying its design.


Introduction
This article presents the Moore library for interval arithmetic in C++20. It gives examples of how the library can be used, and explains the basic principles underlying its design. It also describes how the library differs from the several other good libraries already available [3,7,11,5,6,14,10,16,15,9,17,18]. The Moore library is not compliant with the recent IEEE standards for interval arithmetic [1,2], and it will never be, but it would fair to rank in the top five in terms of compliance among the libraries in [3,7,11,5,6,14,10,16,15,9,17,18], the first and only truly compliant being [6], followed by [15], which is almost compliant. Of course, the library has limitations, and some of them are addressed in the last section, but only by playing a bit with it you will be able to tell whether its pluses offset its minuses.
The library was written mainly for myself and my students, to be used in our research about interval arithmetic and scientific computing in general. It is also meant to be used by other people, and its open source code and manual are available upon request to me. It is distributed under the Mozilla 2.0 license.
The Moore library will be useful for people looking for better performance or more precise types of endpoints for their intervals. To emphasize this point, Section 7 presents experiments showing that it is competitive with well known libraries, and it is significantly faster than some of them. The library will be most helpful for people using single or double precision arithmetic for most of their computation, with sporadic use of higher precision to handle critical particular cases. In this scenario the Moore library offers tools which are not available "out of the box" in other libraries, if available at all. I assume that you are familiar with interval arithmetic, and understands me when I say that the library satisfies all the containment requirements of interval arithmetic. I also assume that you have experience with templates, but you do not need to be familiar with the feature of C++20 which distinguishes most the Moore library from the others: Concepts [8], which are described in Section 3.
In the rest of the article I present the library, starting from the basic operations and moving to more advanced features, and present extensions of the library for linear algebra and automatic differentiation. With the Moore library you construct intervals by providing their endpoints as numbers or strings, and then use them in arithmetical expressions as if they were numbers. The library also provides trigonometric and hyperbolic functions, their inverses, exponentials and logarithms, and convenient ways to read and write intervals to streams.
The file /moore/config/minimal.h contains the required declarations for using the library with double endpoints. The line UpRounding r; is mandatory. It sets the rounding mode to upwards, and the rounding mode is restored when r is destroyed. This is like one of the options in the boost library [3], but the Moore library uses only one rounding policy. In fact, giving fewer options instead of more is my usual choice. I only care about concrete use cases motivated by my own research, instead of all possible uses of interval arithmetic. I prefer to provide a better library for a few users rather than trying to please a larger audience which I will never reach.
Intervals are represented by the class template TInterval<E>, which is parameterized by a single type E. The letter E stands for endpoint, and both endpoints of the same interval are of the same type E, but intervals of different types may have different types of endpoints, and we can operate with them, as illustrated below. The default value for E is double, so that TInterval<> represents the plain vanilla intervals with endpoints of type double available in other libraries.
The library does not contain class hierarchies, virtual methods or policy classes. On the one hand, you can only choose the type of the endpoints defining the intervals of the form [a, b] with −∞ ≤ a ≤ b ≤ +∞, or the empty interval. On the other hand, I do believe that it goes beyond what is offered by other libraries in its support of generic endpoints, intervals and operations. The library works with several types of endpoints "out of the box," that is, it provides tested code in which several types of endpoints can be combined, as in the example below.
It also implements other kinds of convex subsets of the real line. For instance, it has classes to represent intervals of the form (a,b], [a,b) or (a,b), in which the "openness" of the endpoints can be decided at compile or runtime, and these half open intervals are used to implement tight arithmetic operations.
The code below illustrates the use of intervals with four types of endpoints: which is the appropriate type for storing the convex hull of x, y and 0.3. -It also deduces that RealEnd<256> is the appropriate type of endpoints for the interval representing the intersection of x, y, z and w, and this is the endpoint type for j.
I ask you not to underestimate the code above. It is difficult to develop the infrastructure required to handle intervals with endpoints of different types in expressions as natural as the ones in that code. In fact, there are numerous issues involved in dealing with intervals with generic endpoints, and simply writing generic code with this purpose is not enough. The code must be tested, and my experience shows that it may compile for some types of endpoints and may not compile for others.

Concepts
The Moore Library differs significantly from the previous C++ interval arithmetic libraries due to its use of Concepts, a feature which will be part of the C++20 standard [8]. Concepts improve the diagnostic of errors in the compilation of templated C++ code, and they can be motivated by the following example. Suppose we write the code below to compute the length of intervals of types Interval provided by several libraries. This code works as long as the functions inf and sup are provided, either by the original library for the type Interval or by an adapter. However, it will not take long for someone to code something like the snippet below and get indecipherable error messages about infs, sups and strings.
void unlucky() // code in a source file unrelated to intervals. { std::string str("I know nothing about intervals!!!"); std::cout << length(str) << std::endl; } When reading the error messages about infs and sups of strings in the compilation of the unlucky function, the programmer may not be aware of the chain of inclusions leading to the header file containing the declaration of the function length for intervals, and the length function for strings will be declared in yet another header file. It will be difficult to relate the error messages to the code which is apparently being compiled, and unexperienced programmers will get lost. Even people experienced with templates will tell you how frustrating these error messages can be, and this is indeed a problem with templates.
We could solve this problem by telling the compiler what an interval is. Knowing that strings are not intervals, it would not consider the function template length below as an option for strings, and there would be no meaningless error messages about infs and sups of strings.
template <Interval I> // Telling the compiler that I must be an double length(I const& i) { // interval for this function template to return sup(i) -inf(i); // be considered. } In essence, this is what a concept is: a way to tell the compiler whether a type should be be considered in the instantiation of templates. In the Moore library concepts are used, for example, to tell whether a type represents an interval (the Interval concept) or an endpoint (the End concept), or when there exist an exact conversion from endpoints of type T to endpoints of type E (the Exact<T,E> concept.) We then can code as follows and the compiler will instantiate the appropriate templates. In the end, concepts allow us to operate naturally with intervals and endpoints of different types. The code above also presents an alternative way to enforce concepts: the requires clauses. These clauses make sure that the operator+ will be considered only when there is an obviously consistent type for the output.
Overall, the motivation for concepts is clear and intuitive. Their problems lie in the details and the crucial question: How should we tell the compiler what an interval or and endpoint is (or any concept, really)? I do not know the best answer to this question, and neither does the rest of the C++ community. This is why concepts are taking so long to become part of the C++ standard.
This ignorance should not prevent us from using concepts. They are a great tool, and we can do a lot with what is already available. With time, as concepts and our experience with them evolve, we will improve our code. For now the Moore library tells the compiler in an ad-hoc way what intervals and endpoints are. It basically lists explicitly which types qualify for a concept, and avoids the more elaborate schemes to declare concepts which are already available, for two reasons: First, their current implementation has bugs (it does not handle recursion properly, for instance.) Second, it is difficult to list precisely and concisely all the requirements which would characterize intervals and endpoints. I would not be able to do it even if the current implementation of concepts were perfect.
The last questions are then: do concepts work for interval arithmetic? Are they worth the trouble? I would not have written this article if my answer to these questions were not an enthusiastic "yes!!", and I invite you to try out the library and verify whether you share my enthusiasm.

Input and output
Flexible and precise input and output are essential for an interval arithmetic libary. The Moore library accepts as input interval literals and streams as follows As the code above indicates, the library throws an exception when the string literal meant to represent an interval is invalid. Strings in hexadecimal notation are handled exactly, and by using them for both input and output you can persist intervals without rounding errors. In the other formats the resulting interval is usually the tightest representable interval containing the input, the only exception being contrived rational numbers for which it would take an enormous amount of memory or time to compute this tight enclosure. In these rare cases you may get a memory allocation exception or need to wait forever.
Properly formatted output is important to visualize the results of interval computations, and the library implements an extension of the usual printf format to specify how intervals are written to streams. This extension is needed in order to align numbers properly in columns when printing vectors and matrices. For example, the code below creates a 3 × 3 matrix of intervals (a box matrix) and writes it to the standard output. The output is formatted according to the string "11.2E3W26", which extends the argument "+11.2E" passed to printf to write floating point numbers in scientific notation (E), showing the plus sign (+), with 11 characters per number and 2 digits after the decimal point. We add the suffix "3W26" to the format to ensure that exponents are printed with 3 digits and each interval is 26 characters wide. Without this extension the output would not be as well as organized at it is below.

Linear Algebra
Besides plain intervals, the library provides vectors of intervals, called boxes, and matrices with interval entries (box matrices) The arithmetic operations involving vectors and matrices are implemented using expression templates and one can write code as the one below, which handles the three dimensional vectors x and y and the 3 × 3 matrix a in a natural way. TBox<> z = a * x + 2 * y + x; TBox<> w = tr(a) * y + dot(y,z) * x; // tr(a) = transposed(a)

Automatic Differentiation
The Moore library is part of a larger collection of tools for scientific computing, called Ime library. As part of the work of my student Fernando Medeiros, the Ime library provides classes for automatic differentiation, and I now describe how these automatic differentiation tools by Fernando and myself are integrated with the Moore library. First, we use a function template to declare the function which we want to differentiate. template <typename T> T example(T const& x) { return exp( sqrt(exp(x)/ 3) + x) * (2 * x) -10; } Once we have declared example, it is easy to compute its derivative using interval arguments. For instance, the function newton_step below performs one step of Newton's method for solving the equation f (x) = 0. In this code the type ADT<I> represents the usual pair of function value and derivative used in forward automatic differentiation schemes. The library Ime also provides automatic differentiation for functions of several variables, like in the example below in which we print the enclosure of the function value and gradient of the given multivariate function.

Experiments
This section presents the results of experiments comparing the Moore library with three other interval arithmetic libraries: boost interval [3], Filib [11] and libieeep1788 [15]. In summary, the experiments show that, for arithmetic operations, the Moore library is slightly faster than the boost library, it is significantly faster than the libieeep1788 library, and it is faster than the Filib library. However, in double precision the elementary functions (sin, cos, etc.) in Filib are significantly faster than the Moore library, which is in turn significantly faster than the boost library and the libieeep1788 library. Besides the difference in speed, there is a difference in the accuracy of the elementary functions. When using IEEE754 double precision, due to the way in which argument reduction is performed, the boost and Filib libraries can lead to errors of order 10 −8 in situations in which the Moore library and the libieeep1788 library lead to errors of the order 10 −16 . In fact, in extreme cases these other libraries can produce intervals of length 2 when the sharpest answer would be an interval of length of order 10 −16 .
The Moore library was implemented to be used in my research, and the experiments reflect this. I present timings related to my current research about the stability of barycentric interpolation [12,13,4]. In this research I look for parameters w 0 , . . . w n which minimize the maximum of the Lebesgue function among all t ∈ [−1, 1], for a given vector x of nodes, and I use interval arithmetic to find such minimizers and validate them. The first experiment timed the evaluation of the Lebesgue function for 257 Chebyshev nodes of the second kind [12], with interval weights, at a million points t. I obtained the normalized times in Table 1 (the time for the Moore library was taken as the unit.) This table indicates that for the arithmetic operations involved in the evaluation of the Lebesgue function (1) the Moore library is more efficient that the boost, Filib and libieeep1788 libraries. The difference is slight between Moore and boost (10%), more relevant between Moore and Filib (about 300%) and very significant between Moore and libieeeP1788 (about 25000%).
In the second experiment, myself and my former student Tiago Montanher considered the computation of the roots of functions which use only arithmetic operations, like the Lebesgue function in Equation (1) and its derivatives with respect to its parameters. The data for this experiment was generated with an interval implementation of Newton's method which can use any one of the four  libraries mentioned above. We compared the times for the solution of random polynomial equations, with the polynomials and their derivatives evaluated by Horner's method. We obtained the times in Figure 1, which corroborate the data in Table 1. The first two experiments show that the Moore library is competitive for arithmetic operations, but they tell only part of the history about the relative efficiency of the four libraries considered. In order to have a more balanced comparison, in the third and last experiment I compared the times that the four libraries mentioned above take to evaluate of the elementary functions (sin, cos, exp, etc.) using the IEEE 754 double precision arithmetic. The results of this experiment are summarized in Table 2 below, which shows that the Filib library is much faster than the Moore library in this scenario, and the Moore library is much faster than the other two libraries.
I emphasize that I tried to be fair with all libraries and, to the best of my knowledge, I used the faster options for each library. For instance, I used the boost library on its unprotected mode, which does not change rounding modes in order to evaluate arithmetical expressions. The code was compiled with gcc 6.2.0 with flag -O3 and NDEBUG defined (the flag -frounding-math should also be used when compiling the Moore library.)

Limitations
The Moore library was designed and implemented using a novel feature of the C++ language called concepts [8], and it pays the price for using the bleeding edge of this technology. The main limitations in the library are due to the current state of concepts in C++. For instance, only the latest versions of the gcc compiler support concepts, and today the library cannot be used with other compilers. Concepts are not formally part of C++ yet, and it will take a few years for them to reach their final form and become part of the C++ standard.
Additionally, several decisions regarding the library were made in order to get around bugs in gcc's implementations of concepts and in the supporting libraries, and in order to reduce the compilation time. The code would certainly be cleaner if we did not care about these practical issues, but without the compromises we took using the library would be more painful.
Another limitation is the need to guard the code by constructing an object of type UpRounding. In other words, the code must look like this UpRounding r; code using the Moore library A similar requirement is made by the most efficient rounding policy for the boost library, but that library allows users to choose other policies for rounding, although the resulting code is less efficient. Things are different with the Moore library: as the buyers of Henry Ford's cars in the 1920s, its users can choose any rounding mode as they want, so long as it is upwards. Users wanting to mix code from the Moore library with code requiring rounding to nearest will need to resort to kludges like this one: { UpRounding r; do some interval operations } back to rounding to nearest { UpRounding r; do more interval operations }