Fiery number system, or why 1 + 10 = 100

"10.01 x 10.01 = 1000.1001"
George Orwell. "1010001001001000.1001001000100001"



Is there a positional number system with an irrational basis in which all natural numbers are written with a finite number of digits? In which the number is greater than one, without digits after the decimal point, certainly not integer and not even rational? In which 1 + 10 = 100, and 1 + 1 = 10.01?

Exists. It is called the Bergman system, or the number system with the base Φ (read as “phi”, this is the letter of the Greek, not the Russian alphabet). The number Φ, also called the golden number or the constant golden section, has the following formula:
')

Hereinafter, I will sometimes call it fieric (by analogy with, say, octal) number system, and sometimes I will not.

What it is?

The fiery number system is the usual positional number system with an unusual base. If in the commonly used decimal number system each digit corresponds to a certain tens level (123 = 1 ∙ 10 ² + 2 10 ¹ + 3 ∙ 10 ⁰ ), and in the binary one - to a certain degree of two (101 ₂ = 1 2 ² + 0 2 ¹ + 1 ∙ 2 ⁰ ), then in the Bergman system, in which, as in the binary one, there are only the digits 0 and 1, each unit symbolizes a certain power of F. For example:

Where did you go?

As you might guess from the name, the Bergman system was invented by a certain Bergman. Perhaps you have a question, what kind of charismatic bearded man is depicted at the beginning of the article. So, this is George Bergman, a mathematician-algebraist, a professor at the University of California at Berkeley. He was born in Brooklyn in 1943, and fourteen years later, when he still had no beard or doctoral degree, but already had imagination and interest in abstract algebra, published an article in Mathematics Magazine, in which he described the number system ( he himself called it "tau-system"), its basic properties and the rules of arithmetic operations in it. In his article, he admitted with decent respect for modesty that he "sees no useful use for number systems like this, besides entertainment and exercise for the mind." Time has shown, however, that in his assessment he was not quite right. However, we will talk about the application of the fieric number system later.

What is interesting?

There are infinitely many numbers of systems with an irrational basis that allow you to record any natural number with a finite number of digits. For example, a number system with a base equal to the square root of two. If you use only every second digit (those that correspond to even degrees of the base), then it can be used as a usual binary number system:

Similarly, the square root of three, the cube root of two will suit us as a base ... Well, you get the idea. Number systems, in which almost all integers will be written with an infinite fraction, are also quite a few. I will tell you a secret
Strictly speaking, any system with a transcendental base and a sufficient set of numbers has this property. In pi-echny, e-aychny and even in e-in-degree-pi- ny system of numeration, all natural numbers greater than one will be written as an infinite fraction.

The Bergman system is different from the first and the second group. In it, any natural number greater than one has a nonzero, but finite number of digits after the decimal point. For example:

2 = 10.01 _F
5 = 1000.1001 _F
42 = 10100010.00100001 f
451 = 1010000001010.000100000101
1984 = (see epigraph)

Simply put, it breaks the pattern a little. We are used to the fact that the concepts of “signs after the comma” and “fractional part” are obviously interrelated. However, in the fieric system, the fractional part may be zero, and the number of digits after the decimal point may not be equal. Moreover, it can be proved that if the number of digits after the comma equals zero, then in all cases except zero and one the non-zero fractional part is non-illusory present.

In addition to integers, a finite number of characters in the fieric number system also contains numbers from ℤ (F), that is, all numbers of the form:

As the attentive reader may have noticed, there has not been a case in one of the above-mentioned records that resulted in two units running in a row. This is not an accident. As in the Fibonacci number system , in the Bergman system, the highest-order unit is the sum of two smaller units. In other words, 100 _F = 11 _F. This is due to the unique property of the golden section: ² = + 1. Therefore, a canonical recording of a number in the fieric system is one where no two units go in a row.

How to translate it?

For natural numbers, Bergman suggested the following algorithm: if we know the notation of the number n, then we look at her number in the zero position, before the comma. If there is zero, write one there and get n + 1. if there is already one, then we will denormalize the number entry, applying the rule 100 = 11 to this unit. If one of the newly formed units falls into a place already occupied by another unit, we first convert it, and so on. Then in a denormalized record, we change zero by one and normalize it back. For example:

4 = 101.01 _F = 101.0011 _F = 100.1111 _F
5 = 101.1111 _F = 110.0111 _F = 1000.0111 _F = 1000.1001 _F

The proof of the correctness of this algorithm (which I leave to the conscience of the reader) implies, in particular, that any natural number has a finite representation in the fieric number system. I have already spoken about this before, but now you don’t have to take my word for it.

This algorithm has a rather sad temporal complexity. You can optimize it as follows: instead of the blunt addition of one, we will alternately multiply by two and, if necessary, add one (for example, we get the value of the number from its binary notation). However, multiplying by two, it’s the addition of a number with itself, in the Bergman system is not a completely trivial operation, which we will discuss later.

On the other hand, we can find in the linear time the fieric notation of a number stupidly by definition. This algorithm can be roughly described by the following js code:

const Phi = (Math.sqrt(5)+1)/2; function toPhiBase(n){ var power = 1; var result = ""; while(power <= n){ power *= Phi; } while(n > 0){ if(power == 1){ result += "."; } power /= Phi; if(power <= n){ n -= power; result += 1; }else{ result += 0; } } return result; } 

Seeing this code, a person familiar with programming, of course, should be discouraged. In his head should be thought about floating-point numbers, loss of accuracy, futility of life ... Indeed, the above function will not work correctly for even a small number of the same number, like the same 1984. The implementation has pumped up, but this does not mean that the idea is bad.

If we work with floating point numbers, a loss of precision is almost inevitable. But you can not work with such numbers. You can conduct all operations in the field ℚ (√5) (that is, in the field consisting of numbers of the form a + b √ 5, a, b ∈ ℚ). Actions on such numbers can be implemented using only operations on rational numbers. And operations on rational numbers can be implemented using only the addition, subtraction and multiplication of integers that do not lead to a loss of accuracy. In short, you can write your little symbolic arithmetic . And I always wanted to write it.

As soon as I realized how much the inhabitants of the Internet suffer without the ability to transfer numbers to the Bergman system and back, I immediately nava- npm-module based on the above approach. Now everyone can independently check if I made the number 42 in the fieric notation by typing something like this into the console:

 npm install phibase
 node
 var PhiBase = require ("phibase")
 PhiBase.toPhiBase (42) 

Those who, for some unclear reason, have not installed node and npm, can use the online converter

By the way about the transfer back. Here again, there are several approaches. It is possible in the style of Bergman to take out from the number one by one, if necessary, denormalize his record. You can count by definition in floating point numbers, resigned to the loss of accuracy (I will not give the algorithm, it is quite obvious). Or, in dealing with rational numbers, you can again use the "symbolic" calculations - in my module, as you might guess, this method is used.

How to work in it?

Short answer: hard.

Classical addition and subtraction algorithms do not work in the Bergman system. As we remember, 1 _F + 1 _F = 10.01 _F. This means that if you try to add "in a column", the emerging hyphenation will go both to the left and to the right. It deprives us of hope just to take numbers from some end and add, transferring surplus to the other end. One of the approaches to addition in the fieric system is that, to begin with, we add numbers simply as vectors of digits (10.01 + 101.01 = 111.02), and then somehow normalize the record. The original (in the sense, the original) approach proposed by Bergman was as follows: writing the numbers one over the other, denormalizing them in such a way that two units were not in the same discharge. After that, we add them one by one (adding zero to one or zero to zero is no longer a problem for a trained mathematician), then normalize the sum.

This approach seemed so funny to me that I wrote a small game that allows the player to feel all his charm personally.
Multiplication and division, however, are implemented in a more or less standard way - multiply into a bar, divide by a corner.

And why is it needed?

In an amicable way, this section should not be written by me, but by some stern engineer of the Soviet hardening. As far as I know, the Bergman system has been used in some ADCs . It was supposed to use its redundancy for greater noise immunity, but the “iron” implementation of such a converter was prone to errors, and the idea was sent to the box. I would love to say more, but I can’t, and honestly admit my incompetence. I hope someone from the readers knows more - in this case, I will gladly post here a link to his informative comment.

janatem suggests in his comments that if you add the special number "-1" to Bergman's system, then the resulting symmetrical number system will have a very useful feature: the possibility of parallel bitwise addition. In other words, in it it is possible to get some digit of the sum of numbers, without calculating the previous ones for this. In the decimal number system it is impossible: in order to surely know from which digit the sum of 999995 + x (x is a digit) will begin, we definitely need to know the value of x, despite the fact that this digit is five digits from the one that really interested in. Such bit independence can be used to radically accelerate computations on certain architectures.

Oh yeah, I almost forgot. Another fiery number system can be used to multiply integers. This is done as follows:

1. One of the numbers is translated into the fieric number system and is recorded somewhere, preferably on checkered paper.
2. The other is written out in the cell under the zero digit of the first number.
3. To the left of the second number we write an arbitrary third number — generally any.
4. We continue the series of the second and third numbers to the left and to the right so that each number in the series is equal to the sum of two numbers to the right of it. It turns out something like the Fibonacci series, only built on other initial numbers and directed from right to left.
5. Sum up all the numbers in this series, over which the units are written. This amount will be the desired product.

If you are bad with multiplication, but you can quickly translate numbers into the fiery number system and build fibonacci-like rows, this method is definitely for you. The proof of its correctness is based on the fact that if the record is denormalized at the top, the sum of the numbers under its units will not change.

And it's all?

There are a few more things that I would like to say at last. First, if you tortured my online converter properly, you might have noticed that fractional numbers in the fiery number system, like in any other positional number, are recorded as a periodic fraction. The proof of this fact is based on the division by a corner and again does not differ from the proof carried out in the number system of a healthy person.

Secondly, I lied to you when I spoke about the "unique property of the golden section." It is, of course, unique, but not quite. The equation x ² = x + 1 has another solution, equal to

In a system with a base φ _- (let's call it anti-spherical), all properties of the fieric system are preserved, which are derived from the identity 100 _F = 11 _F. In particular, all integers have the final notation in it (and the same as in the fieric system). This is especially funny, because the new foundation is not only irrational, but also negative and less than one in absolute value. One can even prove the following theorem: if a number has the same final entry in the fieric and anti-realic number system, then it is integer.

Finally, in the fiery number system, the formula for the number Φ can be rewritten as follows:

Tsimes is that the above formula, if we consider it as an equation, has a unique real solution. That is, in fact, it can be used as a definition of F.

Think about it.