Some Basic Functions for Composite Arithmetic

Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 49

Abstract¶

This paper briefly describes proposals for a standard general purpose arithmetic called composite arithmetic, gives special attention to the register form of that proposal, reviews some of the basic functions needed for that arithmetic, compares those functions to the practice followed by APL and J, and urges the APL/J community to support and contribute to the establishment of a standard for composite arithmetic.

Introduction¶

That a recently published proposal for a standard for general purpose arithmetic[1] should have an APLish flavour is not a coincidence. The proposal followed directly from dissatisfaction with the ideas expressed in an earlier paper published in Quote-Quad[2] which itself arose from a consideration of extensions made by J[3] to the system traditionally used by APL to represent numbers.

The proposal also embraces a viewpoint on automatic calculation which characterizes APL and other typeless programming notations, the viewpoint which holds that users of a notation should not have to make decisions about how numbers shall be represented that could be better made automatically.

The composite arithmetic proposal goes further than this in holding that calculations that can be done exactly should be done exactly, and if they can’t then the trustworthiness of their results should be made plain. In this, the proposals go beyond APL’s present compass.

Adherence to these principles means that the representation of numbers and the machinery that is needed to work on those representations are more complex than say the traditional so-called floating point representations and machinery[4]. But composite arithmetic can also be more reliable under the kind of extreme conditions that the users and designers of APL interpreters take pride in being able to deal gracefully with. And improved technology now makes such complexity practical.

The purpose of this paper is to outline the central area of the composite arithmetic proposal, and to disclose some of its difficulties, in the hope that APL people might bring their very particular experience in the area to improve the proposal and to promote work towards getting a general purpose arithmetic standard adopted.

Composite Arithmetic¶

The proposal for composite arithmetic proposes three forms for the representation of numbers, where by forms is meant sets of closely related formats.

1. Storage form is for the efficient storage of numbers in data and program files. Binary encoding is used.
2. Register form is for the effective storage of numbers undergoing arithmetic. Binary encoding is used in a long accumulator format [5].
3. Display form is for the clear and truthful display and input of numerical values. Character encoding of a variety of decimal representations is used.

Since all arithmetic is carried out notionally on register form values, all conversions between forms are as shown in the following diagram.

┌─────────┐         ┌──────────┐         ┌─────────┐
│ storage │--->-----│ register │---<-----│ display │
│  form   │---<-----│   form   │--->-----│  form   │
└─────────┘         └──────────┘         └─────────┘

The main concern of this paper is to consider the operation of some of what to APL people are primitive functions, otherwise to be known as arithmetic operations. The results that can be given by these functions are limited by the means available to represent those results in register form. Therefore the main explication of this paper must be preceded by a short description of register form.

The proposed composite arithmetic anticipates that results, though they are always produced in register form, will normally be stored in files in much shorter storage form[6], and presented to users, and keyed in by them, in the much more familiar display form[7]. Register form, being much longer, is not expected to be used normally for the long term storage of results.

Values are encoded binarily in register form, but, for the purposes of explanation here, a decimal encoding is needed for use in explanations. In what follows, it is therefore convenient to use the proposed composite arithmetic’s display form conventions in giving examples and values. The following summary merely gives a basis for understanding display form, in advance of explanation of different kinds of values as they are needed in describing register form. A summary of display form is given in a companion article in APL Quote-Quad [7] prepared before this one.

Display Form¶

The approach suggested for the display form of composite arithmetic is to suppose a poor character set (such as ASCII or EBCDIC) and a rich character set (such as is easily supported by modern printers), and to define alternative usages for the two. Because this paper is being keyed in on an ASCII machine, only the poor alternative is used here.

The decimal digits are the basis for display form. However, composite arithmetic requires that credible digits be distinguished from dubious digits. In this paper the underline character signals the onset of dubiety. Thus 1234 represents an exact value. However, 12_34 represents an uncertain or inexact value, but guarantees that it is somewhere in the range 1184 to 1284 including both the extremes and all the integral and nonintegral intervening values.

Beyond the digits themselves, certain punctuation marks are used to compose number representations. These are shown in the following table alongside examples of their usage.

Register Form¶

Register form comprises four formats, all of the same length, namely 4096 binary digits. Which format is used depends on the kind of value loaded into it from one of the other forms, or from a calculation. The arithmetic chooses the format, not the programmer.

┌──────┬─────────────────────────┬──────────────────────────┐
│ tags │         v a l u e       │      f i e l d ( s )     │
└──────┴─────────────────────────┴──────────────────────────┘
4095   4091                     2047                         0

The first four bits of register form are used for tags. The first two tag bits specify the format in use, along the following lines. (The original proposal [1], for simplicity of presentation, described only three formats, subsuming the integer within the rational.)

An integer of format 00 takes up all the bits that aren’t tag bits, all 4092 of them, but the other three formats have a separation point in the middle of the form, so that for format 01 the low order denominator is 2048 bits long and for the other formats the same low order 2048 bits are used for the fractional part of the representation. The numerator of format 01 is 2044 bits long, and the sign of the rational value is kept in the fourth tag bit.

Between them, formats 00 and 01 allow exact arithmetic to be applied to a great range of values, typically to produce exact results. Whether or not such results can be put into exact storage or display forms is another question, but the arithmetic is without error of calculation on such values. The provision of a rational form means that even divisions are carried out exactly for typical exact divisors and dividends.

Certain special values are standardly represented. Exact zero and two infinities, represented strictly as 0 1r0 and ¯1r0 in display form, are coded in the third and fourth tag bits of format 00. Indefinity, a value including arithmetic indeterminacy [8] and represented strictly as 0r0 in display form, is coded in the third tag bit, and the arithmetic sign is coded in the fourth tag bit, of format 01. Other special values are coded into inexact formats, but inexact formats are more complex, and need particular explanation.

The sheer size of register form means that the majority of inexact arithmetic, the arithmetic customarily carried out on so-called floating-point representations [4], is actually carried out on very long fixed point representations, and so has the potential to give very accurate results.

It is perhaps worthwhile to review here the difference between accuracy and precision, given that the terms are often confused [9]. Precision is about how exact the representation of a number is, whereas accuracy is about how well the representation expresses the value it represents. Thus, 3.24159 is precise to five decimal places, but as a value of π it is not even accurate to one decimal place.

Inexact Formats¶

Two register formats are proposed to hold inexact values. These formats are more complex than the exact formats because they are designed to keep a record of accuracy. For this, both formats include a pointer to the last credible bit in the value, that is, to the rightmost bit of completely reliable value. The other bits are here called "dubious". Thus the arithmetic is required to keep track of reliability. Note that the dubious bits are not negligible because they mark the centre of the interval of unreliability. (The original proposal [1], again for simplicity, only mentioned reliability tracking in passing, but its importance warrants its inclusion in composite arithmetic from the beginning.)

┌──────┬───────┬──────────────────┬──────────────────────────┐
│ tags │ doubt │  i n t e g e r   │      f r a c t i o n     │
└──────┴───────┴──────────────────┴──────────────────────────┘
4095   4091    4079              2047                         0

Both the inexact register formats hold signed values with a fractional part, and in twos complement form.

The first inexact format (10) keeps its value directly, the second (11) keeps its value as its binary logarithm. The long accumulator design of the register [5] means that the vast majority of inexact arithmetic can be done in the first format, and the second format is called into use only when results from the first format overflow or threaten to lose accuracy.

Certain special inexact values need to be held in register form. The first such class of special values is that of the inexact zeroes, and the second class is that of the reciprocals of such values. These two kinds of values are effectively intervals which include zero or infinity. The third tag bit signifies which class, and the inexact infinities are represented by their reciprocal, which is apt because they are usually generated by an inexact zero divisor. An interval including both positive and negative values is called "double", the other kind "single".

These special inexact values arise, because inexactness is being acknowledged and kept track of, when all significant digits are dubious. The arithmetic intended for inexact values is a kind of interval arithmetic [10]. The proposed standard does not constrain the arithmetic to this particular kind of arithmetic, but does require any arithmetic operation to maintain at least as much accuracy as arithmetic carried out directly on register form would. An implementation could include better arithmetic, but the arithmetic implied by the register format as defined is a kind of hybrid of conventional range arithmetic [11] and significance arithmetic [12].

In inexact register formats, the full value normally gives the centre of the interval, and the doubt pointer indirectly gives the width of the interval. In the primary format the centre is the arithmetic mean of the ends of the interval, in the secondary format it is normally the geometric mean. Inexact infinities in either format, and all double intervals in secondary format, need exceptional representations which it is not relevant to review here.

The Arithmetic¶

The results of any arithmetic, that is, of the application of any arithmetic operations to register form values, is straightforward for straightforward values. But there are two broad classes of values that are not straightforward, the inexact and the special.

An examination of the arithmetic of certain operations, then, is largely an examination of the results when they are applied to inexact and to special values.

However, there are some general rules. Indefinity yields indefinity. Otherwise, inexactness yields inexactness. Otherwise, exactness yields exactness.

Of course, the application of such rules depends on the particular arithmetic operation. The arithmetic operations are what APL has traditionally called primitive functions. Since it is usual in discussions of computer arithmetic to talk of instructions operating on data, the APL tradition is inappropriate here, but it is useful to contrast monadic operations and dyadic operations.

Just what operations are provided in a standard is a matter that can only be decided after considerable discussion. Basic monadic operations like negation and magnitude and maybe reciprocal are necessary, and the dyadic operations of addition, subtraction, multiplication, and division are also necessary. And there are many other possibilities which would spring to the mind of an APLer.

There are other operations which might be considered necessary to deal with some of the aspects peculiar to composite arithmetic, in particular to inexact representations.

Operating on Instructions¶

A primary requirement is to be able to test whether a value is exact or not. But this test should not be considered in isolation. Given that testing is needed, what tests are needed beyond exactness?

The traditional tests result from comparison of two values, and are basically tests of whether the first value is equal to, or is greater than, the second, or some combination of these two and their opposites. For exact values in composite arithmetic, these tests are straightforward, and could easily be specified and provided. But it is not so for inexact or special values. It is extremely unlikely that one instance of _1 (not negative, but entirely dubious, being in display form a particular value somewhere between ¯4 and 6) would equal another, or that _1 would equal _01, and it is at the very least debatable whether 1r0 even equals itself.

The way around this is to revert to the idea that comparison is fundamentally testing the nature of the result of a subtraction of the two values being compared. Under composite arithmetic there is a need to be able to test for different kinds of values, and comparison can then be subsumed under such testing as simply the special case of testing the result of a subtraction.

Values can be different in kind along three dimensions, namely

• exact/inexact
• positive/negative/signless
• normal/indefinite/infinite/zero,

where "signless" is meant to include the ambiguity of a double interval of uncertainty in the case of an inexact zero or infinity. These three dimensions are not truly orthogonal since some combinations cannot occur, for example, an exact signed zero. It is maybe also necessary to be able to test whether a value is primary or secondary, but this is somewhat redundant.

In the case of comparison, now, the subtraction of two normal values would yield an exact zero if they were both exact and equal, and an inexact zero if either or both were inexact and the two were possibly equal.

It is of interest to note that there is not, in composite arithmetic as described here, any need for the comparison tolerance familiar to APL users. Comparison tolerance is fairly complex because it is a regularly implied doubt intermittently applied. In composite arithmetic, the comparison of two exact values is, appropriately, exact. If at least one of the values is inexact, then the actual tolerance is not absent but implicit in the result.

Monadic Arithmetic Operations¶

Only the relationship between one value and its result need be considered for monadic operations in composite arithmetic. In this sense they are simpler than dyadic operations. Of main interest is the behaviour of different kinds of values rather than of any specific value.

Negation and Magnitude¶

Negation and magnitude operations are closely related. In both, negative values are converted to positive values of the same magnitude. Otherwise, for negation positive values are turned to negative ones of the same magnitude.

Indefinity and exact zero are unchanged by the operations. Exact values yield exact results, except only for the lowest possible integer value, whose positive equivalent cannot be represented exactly in register form. Interestingly enough, this maximum negative integer value would have to converted straight to secondary inexact format because it would be much too big for the primary format.

Inexact values yield inexact values with unchanged doubt, again except only for the lowest possible primary value, which would have to be converted to secondary, or maybe to the maximum positive value with an extra bit of doubt.

Floor and Ceiling¶

Floor and ceiling monadic operations, familiar primitive functions for experienced APL people, have a lot of interest in composite arithmetic because they can change the very nature of a value, for example by converting an inexact value into an exact one. The two operations can be considered together, as the ceiling operation is only systematically different from the floor in a fairly obvious and consistent way.

Firstly, exact infinities and zero, indefinities, and integer values would all be unchanged. All rational values would be changed to integers. Some inexact values could be changed to integers, providing their interval did not have an integer value within it, and this could apply also to inexact zeroes with single intervals.

Inexact values whose doubt extends their interval across at least one integer, in particular all inexact zeroes with double intervals and all inexact infinities, would remain inexact, though their centre point might change. Indeed, just what the change of centre point in these cases should be could make an interesting study.

Centre and Tolerance¶

Operations that provide a breakdown of inexact values are needed, and the two obvious ones would give the centre of the interval of uncertainty and its radius (or tolerance). From these two values the limits of the interval can be calculated simply by addition and subtraction for all but inexact infinities.

Applied to exact values, the centre operation leaves the value of its operand unchanged, and the tolerance operation yields an exact zero. This can fairly arbitrarily apply also to indefinity and exact infinity. Inexact values never yield a tolerance of exactly zero, so taking the tolerance of a value also provides a check on whether it is exact or inexact.

For inexact values the centre operation will give an entirely credible value, that is, an inexact value with all its value bits credible. For primary inexact values this will merely involve changing the doubt to zero, but for secondary inexact values this involves calculating the arithmetic mean of the limits of the interval so that the limits can still be calculated by adding the tolerance to, or subtracting it from, the centre.

The tolerance of inexact values is derived from their doubt, and is itself entirely credible. It will either be an inexact zero, or a positive non-zero. Of interest, though, is the question of the circumstances under which the tolerance of a secondary inexact value should be given in primary format, as at least the tolerance of the centre of a secondary inexact value must be, since an entirely credible inexact zero cannot be represented in secondary inexact format.

Inexact zeroes, being always primary, can be handled the same as ordinary primary inexact values. Inexact infinities, however, must be anomalous, since their centres aren’t any sort of mean of their limits. And what should the centre of a double infinity be ? Probably the best result would be an indefinity. And if the centre of a single infinity is taken as the appropriately signed infinity (exact?), as it must be, the tolerance is infinite, and, even if it wasn’t, the limits can’t be calculated in the usual way because, apart from any other trap, subtracting the infinity of a tolerance from the infinity of a centre gives an indefinity, which is no kind of limit at all.

Dyadic Arithmetic Operations¶

The consideration of dyadic operations requires consideration of the results arising from combinations of various kinds of operands. The consideration is richer both because of the much greater number of cases of operand kinds, but also because the nature of dyadic operations is typically more complex than the nature of monadic ones.

Higher and Lower¶

The higher and lower operations are very similar, and simpler than most other dyadic operations, so they serve as a useful starting point. These are sometimes called "greater" and "lesser", which is misleading, because these words really, in the ordinary meanings of these words, apply to the magnitude of operand values — clearly ¯1000000 is greater than 0.0001 even though it is lower in the number line. Linguistic considerations aside, only the higher operation need be considered here, since the operation of the lower can easily be inferred from it.

The result of higher is indefinite when an operand is indefinite. Positive infinity is higher than any definite value, and any definite value is higher than negative infinity. The higher of any two other exact values is standardly determinable simply from their relative position on the number line.

The result of higher when one operand is inexact and the other ordinarily exact is slightly more complicated but can be fairly easily pictured by imagining the two operands depicted on the number line. The exact value occupies a point, the inexact covers an interval. If the exact value is outside the interval and lower than it, then the inexact value is the result. If the exact value is outside the interval and higher than it, then the exact value is the result. If the exact value is inside the interval, then the exact value is the lower limit of the result and the upper limit of the inexact value is also the upper limit of the result.

In this last case a very important principle may be involved. While the lower and upper limits of the interval of the result may be specifiable and calculable, the interval may not be exactly representable in a register format. In this case the result must be the representable interval of least tolerance that encompasses the interval that can’t be represented.

The combination of one exact and one inexact operand is closely analogous to the situation with two inexact operands where the tolerance of one of the operands is zero. The case of particular interest is where the two intervals overlap. Here the lower limit of the result is the higher of the lower limits of the two operands, and the higher limit of the result is the higher of the higher limits of the two operands. This is quite a general statement if exact value are considered to have two limits of the same value.

One remaining troublesome case remains, and that is where an operand is a double inexact infinity. The result is indefinite.

Addition and other Arithmetic¶

The considerations for the addition operation are somewhat the same as those for higher and lower. For the general case, the lower limit of the result is the sum of the lower limits of the two operands, and the higher limit of the result is the sum of the higher limits of the two operands. As for the higher and lower operations, particular behaviour is involved for particular kinds of operands, with double inexact infinities giving indefinite results, as also do adding infinities exact or inexact of opposite sign.

As for the subtraction operation, it is tempting to define it in terms of the addition of the negated right operand. This would be a mistake because then the subtraction by the largest negative integer would almost always give a secondary inexact result, whereas an exact result will often be more appropriate. Similarly, division should not be defined as multiplication by the reciprocal.

One group of operations could prove particularly useful for the manipulation of inexact values. These are the remainder, the quotient, and what might be called the bulk operation because it yields the product of the quotient and the divisor or modulator. The quotient is always an integer, and when the modulator and the divisor are exact then the bulk is also. The result of the bulk operation might be thought of as the extraction of as much of the dividend as can be put together from units of the modulator. The bulk plus the remainder reconstructs the dividend. However, these operations become complex when the modulator is inexact.

Conclusion¶

The paper outlining the proposal for using composite arithmetic as the starting point for a standard general purpose arithmetic also gives reasons why such a standard is needed to complement the highly successful binary floating-point arithmetic standard [1].

The floating-point standard is a relatively simple one, being mainly concerned with part of what is for composite arithmetic called storage form, and with the arithmetic to be carried out on values in that form [13,14].

Composite arithmetic needs three forms, and this paper has outlined the proposals for its register form, and for some of the arithmetic to be carried out on values in that form, a form on which the floating-point standard is silent [see also 15].

APL/J users and developers have long and most unusually relevant experience with the type-less style of calculation proposed for composite arithmetic. Should the APL community, particularly those members belonging to the IEEE Computer Society, agree that a standard like the one proposed would be of benefit in exposing and promoting the kind of computational approach that APL has for so long (and for so little popular result) promoted and embodied, then that community has an opportunity here to help build support for a standard for general-purpose computing, and to contribute significantly to making that standard as good as possible.

References¶

1. W.N. Holmes, Composite Arithmetic: Proposal for a New Standard, IEEE Computer, Vol.30, No.3, 1997 March, 65-73.
2. W.N. Holmes and C.B. Hallam, The Philosophy of Nothing and Everything, APL Quote-Quad, Vol.25, No.4, 1995 June, 75-82.
3. K.E. Iverson, A Dictionary of APL, ACM APL Quote-Quad, Vol.18, No.1, 1987 September, pp.5-40 (the beginnings of a distinct J).
4. D. Goldberg, What Every Computer Scientist Should Know About Floating Point Arithmetic, ACM Computing Reviews, Vol.23, No.1, 1991 March, pp.5-48.
5. U.W. Kulisch and W.L. Miranker, The Arithmetic of the Digital Computer: A New Approach, SIAM Review, Vol.28, No.1, 1986 March, 1-40.
6. W.N. Holmes, Composite Arithmetic, A: Storage Form: A Proposed Draft Standard, ftp://ftp.comp.utas.edu.au/pub/nholmes/ca/dssf.ps.
7. W.N. Holmes, Composite Arithmetic and Number Display, APL Quote-Quad, (submitted for publication).
8. H. Davies, Infinity Arithmetic, Comparisons and J, APL Quote-Quad, Vol.25, No.4, 1995 June, pp.28-34.
9. R.J. Fateman, A Review of Mathematica, Journal of Symbolic Computation, Vol.13, No.5, 1992, pp.545-579.
10. G. Alefeld and J. Herzberger, Introduction to Interval Computations, Academic Press, New York, 1983.
11. O. Abert and M.J. Schaefer, Precise Computation Using Range Arithmetic, via C++, ACM Transactions on Mathematical Software, Vol.18, No.4, 1992 December, pp.481-491.
12. L.H. Gray and J.C. Harrison, Normalized Floating-Point Arithmetic with an Index of Significance, in Proc. Eastern Joint Computer Conf., AFIPS, Vol.16, 1959, pp.244-248.
13. ANSI/IEEE Std. 754-1985, Binary Floating-Point Arithmetic, IEEE Press, Piscataway. N.J., 1985.
14. D. Stevenson, A Proposed Standard for Binary Floating-Point Arithmetic, IEEE Computer, Vol.14, No.3, 1981 March, pp.51-62 (accompanies other articles on the proposal).
15. W.N. Holmes, Floating Point and Composite Arithmetics, in Computational Techniques and Applications, ed. J. Noye et al., World Scientific, Singapore, 1998, pp.305-315 (see also ftp://ftp.comp.utas.edu.au/pub/nholmes/ca/ctac97.ps).