Dissipative Arithmetic

What is Dissipative?

A physical system is dissipative is open and allows energy and/or matter to flow through it. Often dissipative systems are far from thermodynamic equilibrium. By analogy computer arithmetic is dissipative in the sense that information can flow through it, but in the process data values are transformed and information is lost.

Computer arithmetic is not reversible. In the sense that give the output of an arithmetic expression, it is (in general) impossible to infer its inputs. E.g. a = x + y

If a = 4.0, then x may be 2.0 and y also 2.0 or x may be 1.1 and y 2.9, or x=0.499999 and y=3.5, etc., etc.

Dissipation causes Robustness

Perhaps counter intuitively arithmetic is robust, in the sense that small changes tend to get lost. In small expressions this is not pronounced. In the above a = x + y example, if we change x then the output a will change. However if the expression is large and the change to x has to filter through many intermediate levels, the impact of the change tends to get smaller until eventually it cannot be seen at all.

Note a change might be visible from a mathematically pure point of view but here we say it is not visible, if when we test it the new arithmetic expression gives the same value as the earlier version. Often, if we spend more effort testing, then the change is more visible, e.g. in the sense that that more tests show a difference. However testing resources are always finite.

Experiments show small syntax changes can be totally lost in large rational functions composed of the four common arithmetic operators addition (ADD), subtraction (SUB), multiply (MUL) and division (DIV). Notice that all four functions are binary, i.e. they take exactly two arguments.

In floating point arithmetic, division by zero leads to infinity and other non-finite values. These propagate immediately through the whole expression often giving a non-finite answer. In such expressions almost any change will be undetectable as the result will still be infinity (or not a number, nan).

To keep arithmetic finite, we protect division by defining divide by zero to give 1.0 i.e. (DIV x 0.0) = 1.0

Representing arithmetic as trees

The arithmetic expression x + 0.997 can be thought of as (ADD x 0.997) where the function ADD performs the addition of x and 0.997

In more complicated expression, we have to use brackets to force the order in which the arithmetic is applied. E.g. (x + 0.997) * -0.052 can be thought of as (MUL (ADD x 0.997) -0.052)

Which in turn can be displayed as a tree:

Notice, conventionally, the root of the tree is drawn at the top of the figure. The root node (in this case MUL) is the one which calculates the final value of the whole expression.

Sampling expressions

The mathematics of trees has been extensively studied. In particular there are fast algorithms for uniformly sampling from the space of all binary trees of a given size [1].

A large Example

We choose one of the trees of size 25001. We chose at random a subexpression within it and replace it with another sub expression, also chosen at random from a tree of 25001 components (shown in red in Figure 2). (This example was chosen because it has one of the longer chains of blue nodes and because it is not easily explained by operations on infinity or multiplication by zero.) disruption in blue

Figure 2: Blue line shows the sequence of 92 arithmetic operations which progressively reduce the disruption caused by replacing x by the constant -0.052 in red. The following graphs show the disruption tails away as we move further from the change until eventually it cannot be seen at all. Click for high resolution version of Figure 2.

Animation of both old (blue) and new function (red) each frame at a different blue node in Figure 2. Notice how new functionality quickly overlaps old hiding more and more of it. Crosses + show test cases where they agree exactly. Eventually, after 92 moves up the expression tree, they agree exactly on all test cases and the syntax change cannot be seen. Click for high resolution version

Free Code

[1] Fast Generation of Big Random Binary Trees for genetic programming. RAND_TREE2_FASTER C++ code: (or rand_tree.cc_r1.43 part of GPquick). See technical report RN/20/01

Files in this directory

W.B.Langdon 20 Dec 2020 (last update 31 Jan 2026).