"Perhaps the most beautiful number system is a balanced trinity" - Donald E. Knuth, The Art of Programming, Edition 2.

Many people know that computers store data and work with them using a binary number system. One of the main explanations for this can be found in the circuit of modern computers, which consist of billions of simple and mass-produced transistors and capacitors, which can together represent two states: high voltage ( 1 ) and low voltage ( 0 ).

This design is so common today that it is difficult to imagine how computers can work otherwise. But, in Soviet Russia of the 50s, they worked differently. If you have not heard about this, google Setun , a balanced three-component computer developed in 1958 by a small group headed by Brusentsov at Moscow State University.

Before talking about Brusentsov and Setun, let me explain a little to the threefold balanced number system.

Balanced trinity

Ternary or ternary is a number system in which there are three possible values: 0 , 1 and 2 . In its balanced version, there are three probabilities -1 , 0 and +1 , often simplified to - , 0 and + respectively.

In this form, the ternary values ​​are implied as “centralized” around the midpoint 0 . The same rules apply as to any other number system: the rightmost symbol, R , has its own meaning, and each subsequent symbol has a value multiplied by the base B , raised to a power equal to the distance D from R

Um, let me just give you an example. Let's write 114 :

 +++-0 = (1 * 3^4) + (1 * 3^3) + (1 * 3^2) + (-1 * 3^1) + 0 = 81 + 27 + 9 + -3 = 114 

And in binary (binary):

 1110010 = (1 * 2^6) + (1 * 2^5) + (1 * 2^4) + 0 + 0 + (1 * 2^1) + 0 = 64 + 32 + 16 + 2 = 114 

And, to be sure, the same rules applied for the decimal number system:

 114 = (1 * 10^2) + (1 * 10^1) + (4 * 10^0) = 100 + 10 + 4 = 114 

Cool?

What if we want to submit -114 ? In the binary and decimal systems, we will need to use the new symbol: the sign. In the main memory of a binary computer, this is done either by storing the lead bit, indicating the sign or significantly reducing the number of numbers that we can represent ¹ . It is for this reason that we are talking about signed and unsigned in programming languages.

But in a symmetric ternary system, as we will find out later, in order to represent the reciprocal of a number (an inverted number), we just need to change everything "+" to "-" and vice versa. We do not need any additional information to indicate the sign!

Look here:

 ---+0 = (-1 * 3^4) + (-1 * 3^3) + (-1 * 3^2) + (1 * 3^1) + 0 = -81 + -27 + -9 + 3 = -114 

We will see later that this and several other properties of a balanced ternary system give us some very interesting computational advantages. But now, let's go back to talking about Setun's computer.

Birth of Setun

In the late 50s, there was an exciting period in the computer world: Nathaniel Rochester and his team at IBM recently developed the first mass-produced computer with an in-memory program, the so-called “modern” IBM 701 computer. John Backus and his team invented FORTRAN , the first high-level programming language that has found widespread use. And, perhaps most importantly, the first fully transistor computers, such as the TX-0 and Philco Transac S-2000 , began to develop. A direction was set for the development of binary computers, which later became dominant.

But it was in North America.

At the same time, a group of mathematicians and engineers in Russia under the leadership of Brusentsov and his colleagues Sergey Sobolev is developing other computer systems ² . Brusentsov and his colleagues explore a variety of Western computers and technological advances, and conceptualize the use of transistors to represent binary data. But let's remember that this is the USSR - transistors are not so easily accessible behind the iron curtain. And tube tubes are equally lame both in Russia and in the West!

Therefore, Brusentsov is developing a base element of miniature ferrite cores and semiconductor diodes, which is able to work as an adjustable current transformer. It turns out to be an effective base for the implementation of the ternary logic ³ . It was found that these elements, compared with their binary counterparts, provide higher speed and reliability and require less power to work.

A team of ten people literally built Setun out of nothing, working in a small room filled with lab tables (which they themselves built!). Every morning, team members collected five simple machine elements. They took ferrite cores and, using a regular sewing needle, wound 52 hanks of wire each. The cores were then transferred to technicians who completed the assembly process and assembled them into blocks.

The ternary logic was realized by combining two such ferrite elements and connecting them in such a way that they simulated three stable states. This approach was successful, but the number of required elements was not reduced, since in reality two ferrite cores can potentially be two binary bits, which ultimately gives more information (2 ^ 2) than one ternary "trit" (3 ^ 1) Sad, but at least the power consumption has been reduced!

Setun operates with numbers up to 18 trit, that is, one trit can simulate any number between -387 420 489 and -387 420 489 . A binary computer requires at least 29 bits to achieve this power.

Development of Setun lasted two years, despite the fact that the system was capable of performing operations within ten days from the beginning of the tests, and at that time this was unprecedented. All were released about 50 cars. And although Setun’s computers worked flawlessly for many years in extreme Russian climatic conditions, the project was torn apart by contradictions.

Mostly because of the inability of the manufacturer to justify the mass production of what they regarded as a cheap field of science and "the fruit of university imagination." I think it is safe to assume that Russia was simply not ready to understand the potential importance of computers. In the end, the Setun machines were replaced by binary counterparts that coped with the calculations with the same efficiency, but the cost of operation was higher than twice!

What is special about the ternary system?

As I have already said, there is no need to store the leading bit in it, or more precisely, to indicate the sign. So, there is no concept of integers with or without a sign - all this is just an integer. Thus, subtraction is achieved by simply inverting the operand and applying addition (which is implemented similarly to computers with a binary system). This plus or minus consistency can also reduce the number of transfers required for multiplication operations.

Another useful feature of a balanced ternary system (or any symmetric number system, for that matter) is the probability to realize rounding of floating-point numbers, by explicitly highlighting the integer part of a number, which makes it possible to simplify the implementation of the division. This is due to the fact that the ternary system displays the fractional part of the real numbers.

Let me give you a simple example. The translation into the code of the number 0.2 as follows:

 0.+--+ = 0 + (1 * (3^-1)) + (-1 * (3^-2)) + (-1 * (3^-3)) + (1 * (3^-4)) = 0.33 + -0.11 + -0.03 + 0.01 = 0.2 

And to write 0.8 you need to start with + in the high-order bit, and then just invert the fractional part (for example, 1 + -0.2):

 +.-++- = 1 + (-1 * (3^-1)) + (1 * (3^-2)) + (1 * (3^-3)) + (-1 * (3^-4)) = 1 + -0.33 + 0.11 + 0.03 + -0.01 = 0.8 

Above it can be seen that the selection of the whole part of the trit to the right of the bitwise point is equivalent to rounding: 0.2 becomes zero, and 0.8 becomes unity. Cool!

Programming with tritas and nights!

Ok, back to Setun for the last time. In the late 60s, Brusentsov developed a more modern machine, the Setun-70, which embodied the ternary more clearly. The notion of "trit" was introduced, which consisted of 6 trites (approximately 9.5 bits). Computer Setun-70 was a stack , and therefore instead of machine instructions, which were intentionally called registers for input and output, all operations were performed in two stacks - one for operands (input) and one for return values ​​(output). In order to adapt this design, the machine instructions were written in reverse box-free notation (reverse Polish notation or postfix notation).

In the late 1970s, Brusentsov and several of his students developed a programming language for Setun-70, which was called the Dialogue Structured Programming System (DSSP). While conducting my research ⁴ , I noticed that this is a stack-oriented language (which, however, is not at all surprising), similar to Forth and uses reverse Polish notation. This allows you to write programs in a relatively high level language, but continue to feel "low-level." So much so that its authors had the following message:

DSSP was not invented. He was open. Therefore, the language has no versions, only extensions.

Consider a program on PRSP, which adds a group of numbers:

 1 2 3 4 DEEP 1- DO + 

Let's try to decompose it. In the first column we have a command, in the second - the state of the computer after execution (the operand stack), and in the third I give an explanation:

 1 [1]  1  . 2 [2 1]  2  . 3 [3 2 1]  3  . 4 [4 3 2 1]  4  . DEEP [4 4 3 2 1]  " " (4)  . 1- [-1 4 4 3 2 1]  -1  . DO [4 3 2 1]  ,     .            0. + []   "+"   ,        ,  +      . 

At the end of execution, the operand stack will be empty, and the return stack will be [10] .

About PRSP is written in more detail on the site of Ivan Tikhonov (authors Sidorov SA and Shumakov M.N.).

Future

The development of balanced ternary computers has practically passed into a small footnote in the annals of computer history. And while the study of memory cells capable of effectively representing three different states was insignificant, there were some achievements in this area.

Namely, Japanese researchers at the end of the 90s described the possibility of using the Josephson junction to implement the threefold logic. This could be achieved by circulating superconducting currents — positive (clockwise), negative (counterclockwise), or zero. They found that it gives memory cells "high-speed computational power, low power consumption and a very simple design with fewer elements, thanks to ternary operation."

But I do not think that in the near future you will often come across the concept of a balanced ternary computer. And that PRSP will be a breakthrough from aggressive fans of programming languages ​​- too. But I believe that many wise decisions can be learned from the past. ⁵

(Translation by Natalia Bass )

Footnotes:

1. It depends on how a particular machine represents numbers. An additional code is the representation of numbers in the decimal notation, which makes it possible to represent from -((2^n) / 2) to ((2^n) / 2) - 1 in n bits.

2) Although the Setun computer was the first electronic device to use the ternary system for operation, it is worth noting that the idea of ​​using such a system in computing devices was first popularized more than 100 years ago. In 1840, Thomas Fowler built a computer entirely from wood, and she worked with data using the ternary system.

1. A more accurate description can be found on the website of the Russian Computer Museum .

   
   

2. The reference material for PRSP in English is not very accessible, so I warn you that my knowledge is limited and may contain guesses .

   
   

3. My own contribution can be seen on computerpionee.rs .

   
   
4. The image in the article is taken from the site of the Moscow Supercomputer Complex of Moscow State University , on it one of the Setun machines is in operation.