An introduction and the state of work of the project for the implementation of high-precision arithmetic in an overlaying numeration system, which provides digit-wise parallelism of operations of addition and subtraction of real numbers with restricted carry propagation only by 1-2 bits, is presented. The historical origins of ideas behind such numeration systems in the history of mathematics, dating back to A.L. Cauchy (1840) and L.E.J. Brouwer (1921), are outlined. We explain a simplest overlaying system referred to as "three halves". It is built on the binary system by adding a extra (redundant) third digit representing an interval overlaying with the intervals of 0 and 1. We demonstrate an addition scheme for it, which propagates a carry to next two positions. A simpler scheme with carry propagation to only one position is also shown, and we argue that it requires two redundant digits and a numeration system base not less than 3.
Problem statement. Modern problems of mathematical modeling require an increase in the calculation accuracy and bit width of numbers, some up to thousands or more bits. The digit-wise-parallel implementation of operations on such long numbers faces the carry problem: in the usual column addition scheme, the carry is performed in the worst case in a time proportional to the bit width, while it is intuitively expected that addition can be performed with bit parallelism in one clock cycle. For example, when adding two binary numbers in Figure 1 on the left, the fractional part of the result consists of some units; when replacing the least significant digit of the second number from 0 to 1, there is a carry along the entire mantissa (Figure 1 on the right). There are more complex schemes of carry in logarithmic time [8, Chapter 29], but they have to waste the area of the crystal.
A radical solution could be such a numeration system in which there are no carries
at all for an unlimited number of digits. However, as mentioned by L.E.J. Brouwer a
hundred years ago [
Brouwer was worried about a fundamental mathematical problem that arose in the
development of intuitionistic mathematics: how to represent real numbers and other
(potentially) infinite mathematical objects in such a way that the Principle of Continuity
is fulfilled? It is also called the Principle of Finite information [
The representation of real numbers is (potentially) infinite towards the lower-order bits. The final part of such a representation is a sequence of bits from the most significant to some least significant. Arithmetic operations, for example addition, in order to satisfy the requirements of intuitionistic mathematics, must return each fragment of the representation from the most significant digits, "consuming" a certain finite number of argument digits. However, as we see in Figure 1, if the addition operation in the binary system produces only ones in a row for the leading parts of the arguments, we do not know if it will reset them all to zero at some future moment. Moreover, as we know from the first grade, addition and multiplication in a column are performed from loworder bits to high-order ones, and Brouwer needed other algorithms of operations for real numbers - from high-order bits to low-order ones, since infinity in their provision goes towards the low-order bits.
We observe an interesting phenomenon: seemingly completely different questions from the opposite areas of theory/practice on the axis of mathematics: the foundations of mathematics, on the one hand, and digit-wise parallelization of arithmetic operations, on the other, have been faced same pitfalls. This means that the problem is worthy of systematically tackling it, but you do not need to expect quick, simple results.
Approaches to the solution. The first solution we discovered (thanks to
A.B. Shvorin [
To solve his problem of developing arithmetic operations that satisfy the Principle
of Continuity Brouwer [
Additional digits lead to redundancy in the representation, when the intervals of the numeric axis corresponding to the digits intersect, overlay. Therefore, such systems are called overlaying systems. It is thanks to this redundancy and overlaying that it is possible to "extinguish" the unlimited propagation of carry during addition and to achieve digit-wise parallelism only with local interaction of neighboring parallel blocks. Cauchy and Brouwer each used one additional digit over and above what is required for this reason. You can add more numbers, getting some more benefits (one of which we will show below in Figure 6).
We develop these ideas of the classics further in order to bring numeration systems with redundant digits to practice and implementation of circuitry in equipment.
Other and related works. With the advent of the computer era, and especially in
recent decades, the development of alternative representations of numbers has become
very popular. Many works have been published that cannot be reviewed in a short
paper. Among the recent achievements, we note the work of the group led by Christiane
Frougny [
Another direction with a long history is modular arithmetic based on the residual
class system (RNS). It is interesting that in the USSR in the 1960s, computers based on
modular arithmetic were developed in Zelenograd for use in missile defense systems
[
More detailed historical information about these and other related works can be
found in the introduction of paper [
Status of work and content of the paper. In recent years, the authors, together with
colleagues, have checked the theoretical study of overlaying numeration systems, the
properties, general and special cases of such systems have been studied [
In this paper: 1. An introduction to overlaying numeration systems and a historical background is given. 2. Digit-wise-parallel schemes of addition with carry of only one and two next digit positions in a system with one and two additional digits are demonstrated. As far as we know, the observation that such a scheme is possible was made by us for the first time. In previous works, the problem of reducing the number of additional digits was often solved, which caused a carry to a larger number of digit positions. As a starting point for constructing overlaying systems, consider the familiar binary numeration system. Figure 2 shows the interval [0, 1) of the numerical axis. The parenthesis from 0 to 1 at the top indicates the range of numbers that start at 0. Divide the interval in half. Writing numbers from [0,1/2) starts from 0.0; in the interval [1/2,1) – from 0.1, which is shown by the corresponding brackets.
Before moving on to overlaying systems, we stock up on the observation that representations in the positional numeration system, such as 0, 0.0, 0.1, can be considered an image of not one really number standing at the beginning of the interval, but the interval itself, and, having in mind such semantics, to define arithmetic operations that map intervals to intervals. In this case, it is often necessary to give the answer in the form of an upper bound, generalizing the resulting intervals to wider ones, since the exact intervals will turn out to be unimaginable. This interpretation is not used in conventional positional numeration systems. However, in overlaying systems, on the contrary, the standard interpretation as denoting an exact number gives rise to certain problems, and the interval semantics of operations is convenient and understandable.
Now let's look at the simplest overlaying numeration system, which we call "three halves". The base of the system is still 2, that is, it can be considered binary. However, now we will have three digits: in addition to 0 and 1, there is another additional one, which we represent as ½. This number will represent the interval [1/4,3/4). The numbers, as well as the smaller intervals included in it, will get another image of 0.½ in the first two digits. This interval is shown in Figure 3 in parenthesis below the number axis. Note that the left and right halves of this interval are written using three digits in two ways, for example, the right side – in the form of 0.10 and 0.½ (lower bracket in Figure 3).
We have obtained a system in which an alphabet of a larger number of digits is used
to represent numbers and intervals of the same precision. This requires additional
hardware resources per digit. But it is precisely this redundancy that makes it possible to
"extinguish" the carriers, "absorb" them with additional digits. To see this, it is
necessary to formally describe the tables of addition and subtraction operations. Some of
them are given in paper [
As is known from the theory and practice of conventional positional systems,
symmetric systems with opposite numbers (like the one used by Cauchy [
Figure 4 shows a system with numbers 1, 0, 1. Compared with Figure 3 all labels and designations are shifted by –½ and multiplied by 2. As in Figure 3, the interval indicated by the lower parenthesis in Figure 4 is written in two ways: 0.11 and 0.01.
The carry is now limited to two digits. All calculation paths are finite and have the form: +, s, Π, Σ.
The diagram can be simplified by using a base of at least 3 and two additional digits. It is shown in Figure 7. Here the carry is "absorbed" by one digit position. This happens when the system has a base of at least 3 and contains two additional digits. Here the calculation paths are +, s, DivMod, +.
The paper and the report provide an introduction to the topic of high-precision arithmetic with redundant representation of numbers and the concept of an overlaid numeration system, in which digit-wise parallelism of addition and subtraction of real numbers is possible due to limited carry from a digit position to the next ones. Multiplication and division are also speeded up as they use parallel addition and subtraction.
Computational schemes were presented with a carry by 2 digits for the "three halves" system with one additional digit compared to binary and with a carry by one position for systems with two additional digits and with a base of at least 3.
We are developing circuit designed solutions for the implementation of such arithmetic operations in FPGAs with the further aim of conducting an experimental study of the effect and usefulness of such arithmetic on various applied problems.
It is surprising that despite a rather long history of theoretical study of such systems, we do not know that they have been brought to a convenient practical implementation and widespread testing on applied problems. Perhaps, with all attempts, the desired efficiency was not achieved, and negative results were obtained, which, unfortunately, are not accepted to be published in modern science. On the other hand, it is possible that such arithmetic was inadequate to the previous level of hardware development. For example, today's large volume of circuits loaded into FPGAs creates qualitatively new opportunities than were available before. Understanding the algorithmic problems that still need to be solved and realizing the usefulness only for a limited class of problems, we nevertheless believe that it is necessary to provide users with an implementation of long numbers based on overlaying systems (as well as other representations) in a way convenient for programmers for easy experimentation with problems that require high precision and interval arithmetic.
For applied mathematicians, the ability to freely experiment with new tools is a key factor in their development and bringing them to widespread practice. Mathematicians do not hesitate to answer "yes, come on!" when asked if you want to recalculate your problem with high accuracy and find out how much rounding errors affect the result, even if you need to leave it on a (super) computer overnight instead of getting an answer within an hour on a laptop. But as soon as you tell them that for this you need to rewrite their favorite program in C / C ++ or Fortran, replacing operations in arithmetic expressions with calls to library functions, or recode the program in another language like Python, in which long arithmetic is immediately built into realization, another reaction follows: “no, don't; I'd better go and think."
New high-precision arithmetic – be it modular, overlapped, or simply long-represented in a positional system, whether implemented in a central processing unit or in an accelerator like GPGPU or FPGA - must be seamlessly integrated with popular languages. The transition from programs with ordinary arithmetic (on the types int, long, float and double) to programs with high-precision arithmetic should, in the simplest case, be carried out only by setting some options to the compiler. The implementation of such tools is not a task of developing new representations, algorithms and programs for operations on numbers (which this paper is devoted to), but a common system programming task that requires known resources. Unfortunately, we are not aware of such systems. Their absence is one of the possible obstacles to the development of this direction.
In addition to various mathematical problems, where long arithmetic in hundreds,
thousands or more bits can help to obtain new information from a computational
experiment, we will point out two more classes where the overlaying numeration system
can be advantageous:
1. Overlaying arithmetic is essentially interval arithmetic: a finite set of digits has the
semantics of an interval to which all numbers beginning with this set belong. Thus,
it is applicable wherever interval arithmetic is required to assess the accuracy of
calculations. Such arithmetic has a fundamental drawback: the intervals "spread out"
too quickly and often do not provide any useful information. Therefore, interval
arithmetic should be used in conjunction with long numbers so that it can be easily
recalculated with greater precision, when the accuracy of the current result is
insufficient.
2. Operations in overlaying systems are performed from the most significant bits to the
least significant ones. (Recall that it was for this reason that L.E. Brouwer used it
[
These are topics for future research. 5
Acknowledgements The authors express their gratitude to Arkady Klimov for valuable advice on improving the presentation and paper.
This work was financially supported by the Russian Federation represented by Ministry of Education and Science (grant id: RFMEFI61319X0092).