Complete Arithmetic

[Ulrich Kulisch <ulrich.kulisch@xxxxxxx>]

Occasionally I am getting mails which say something like:

Complete Arithmetic needs a standard of its own.

This indicates a deep misunderstanding.
There is nothing that needs to be or can be standardized for complete airhtmetic.

Complete Arithmetic is designed to compute scalar products and scalar product
expressions exactly. A datum of the type complete is a fixed-point word of the
size L=k+2e2+2l+2|e1|, digits of base b (l number of digits in the mantissa, e1,
e2 least resp. greatest exponent). It covers the full range of the floating-point system 
F = F(b,2l,2e2,2e1) and a few additional digits.  It suffices to allow exact
accumulation (continued summation) of products of floating-point numbers.

For variables of type 'complete' so-called 'complete expressions' are permitted.
As every _expression_ a complete _expression_ is composed of operands and operations.
Only three kinds of operands are permitted:

-- a constant or variable of type real,
-- an exact product of two such objects, and
-- another datum of type complete.

Such operands can be added or subtracted in an arbitrary order.  All operations
(multiplication, addition, and subtraction) are to be exact.  The result is a datum
of type 'complete'. It is always exact. No truncation or rounding is performed
during execution of a complete _expression_.  The result of 'complete arithmetic'
reflects the complete information as given by the input data and the operations
in the _expression_.

Complete arithmetic is a necessary complement to floating-point arithmetic. Although
it looks very simple it is a very powerful tool. A central task of numerical analysis is the
solution of systems of linear equations. The so-called verification step for a system of
linear equations is solely performed  by complete arithmetic. It computes close bounds
for the solution. Complete arithmetic also is a fundamental tool for many other applications
discussed in Chapter 9 of my book Computer Arithmetic and Validity.

In the XSC-languages the functionality of the 'complete' type and _expression_ is available
also for complex data as well as for interval and complex interval data. Corresponding types
are called 'ccomplete', 'icomplete, and 'cicomplete respectively. High speed dot products for
these types would require two complete registers in the first two cases and four in the latter.

Complete arithmetic and expressions can also be defined for higher dimensional data types like
vectors and matrices of the four basic types mentioned in the last paragraph. In the corresponding
syntax diagrams the product would be the matrix vector product and the matrix product respectively.

The data type 'complete' is the appropriate generalization of the long result registers that have
been used on many old mechanic calculators. These also served the purpose to compute dot
products exactly. In German there was a particular word for the process:  "Auflaufenlassen".
Louis Rall once trranslated it into:  "The running total".
 
Best regards
Ulrich

-- 
Karlsruher Institut für Technologie (KIT)
Institut für Angewandte und Numerische Mathematik
D-76128 Karlsruhe, Germany
Prof. Ulrich Kulisch
KIT Distinguished Senior Fellow

Telefon: +49 721 608-42680
Fax: +49 721 608-46679
E-Mail: ulrich.kulisch@xxxxxxx
www.kit.edu
www.math.kit.edu/ianm2/~kulisch/

KIT - Universität des Landes Baden-Württemberg 
und nationales Großforschungszentrum in der 
Helmholtz-Gesellschaft