Numbers - Douglas Crockford report on number systems in life and in programming

Published on September 27, 2017

Numbers - Douglas Crockford report on number systems in life and in programming

    Now computers solve almost any problem. They work and bring benefits in almost all sectors. But let's see what a computer is. This is a machine that manipulates numbers. Such manipulations are practically all they can do. Therefore, the fact that they solve so many problems by simply manipulating numbers seems almost magical.

    Let's see where the numbers come from, where they can lead, and how they work.



    The article is based on the report of Douglas Crockford from the June HolyJS 2017 conference in St. Petersburg (the presentation of the report can be found here )

    Fingers


    Let's start with the fingers. Fingers are much older than numbers. The man developed his fingers to better climb trees and pick fruit. And he was really happy doing this for millions of years.

    Instruments


    But the climate changed, the trees began to disappear. A man had to go down to the ground, walk along the grass and look for other sources of food. And fingers were needed to manipulate tools, such as a stick. With its help, you could dig the earth to find tubers. Another example of a tool is a stone that allows you to chop tubers to make them soft enough to eat (our little monkey teeth do not allow you to eat everything; to survive, we had to learn how to cook).

    Over time, a person gained experience in handling tools. And the tools influenced our evolution, so we continued to update them. Soon we learned how to make knives from volcanic glass, and in the end we learned how to control fire. Now man knew how to plant seeds in the ground and grow his own food. With new knowledge, people began to gather in larger communities. We have moved from families and clans to cities and nations.

    Society grew, and the problem of tracking all human activity appeared. To solve it, a man had to come up with an account.

    Score


    As it turned out, our brain does not remember many numbers very well. But the more complex society became, the more it was necessary to remember. Therefore, man learned to make nicks on wood and graffiti. There were ideas to string nuts on strings. But we still forgot what exactly these numbers represent. Therefore, I had to come up with writing.

    Writing


    Today we use writing to solve many problems: for letters, for laws, for literature. But first they were manuscripts. I consider the invention of writing the most important discovery ever made by man, and it happened three times.

    The first written traces were found in the Middle East. Many smart people believe that this happened in Mesopotamia. I think this happened in Egypt. In addition, writing was invented in China and in America. Unfortunately, the last of these civilizations did not survive the Spanish invasion.

    Let's take a closer look at some historical number systems.

    Egypt


    So the numbers in Egypt looked like.

    image

    The Egyptians had a decimal system. For each degree 10, they had their own character. The stick represented a unit, a piece of rope - 100, a finger - 10,000, and a guy with his hands up - a million (this demonstrates some mathematical sophistication, because they had a symbol denoting not the abstract concept of "a lot", but exactly "a million" - no more, no less).

    The Egyptians came up with many other things: a 3 by 4 by 5 triangle with a right angle (they knew why this corner was needed), a really smart system for working with fractions. They had an approximation for the Pi number and much more.

    Phenicia


    The Egyptians taught their system to the Phoenicians who lived on the territory of modern Lebanon. They were very good sailors and merchants - they sailed across the Mediterranean Sea and parts of the Atlantic. Adopting a rather complicated number system from the Egyptians, they simplified it. Using scripts consisting of only consonants, they reduced the character set from thousands that the Egyptians had to a couple dozen, which was much easier to use. And they taught their system of people with whom they traded, in particular, the Greeks.

    Greece


    image

    The Greeks took the Phoenician system and improved it by adding vowels. Therefore, now they could correctly record all the words. Since then, the Greek alphabet contains 27 letters.

    The Greeks used the same character set to write numbers. They took the first 9 letters of the alphabet to denote the numbers 1 through 9, the next 9 letters for tens from 10 to 90, and another 9 letters for hundreds from 100 to 900. They gave their system to the Romans.

    Rome


    image

    But the Romans still used the Egyptian system as the basis of their number system. Although they adopted the Greek approach - the use of letters instead of hieroglyphs. They also added some innovations to make the numbers a little more compact.

    One of the problems of the Egyptian system was that writing a number 99 required a sequence of 18 characters. The Romans wanted to shorten the record. To do this, they came up with symbols representing half ten or half hundreds (thousands). One of them was represented by the symbol I (or stick), 10 - X (a bunch of sticks connected together), and 5 - V, which is only X in half.

    Another innovation was the addition of subtraction to the number system. So far, systems have been additive. The number was represented by the sum of all characters. But the Romans realized the idea that certain characters (in certain positions) can reduce the number.

    China


    Meanwhile, really interesting things were happening in China.

    image

    They had another system that used characters from 1 to 9 and a set of factors or modifiers. So it was possible to write down numbers of any size and complexity, just making hieroglyphs together. Very elegant system.

    India


    A greater leap occurred in India.

    image

    The mathematicians in India came up with the idea of ​​zero — a number that represented nothing. And they guessed to use it on a positional basis. Only 10 characters were used to display the numbers, but they could be combined to create any number. That was a really important idea.

    Duplicating Ideas


    The Indians handed over their system to the Persians. They called it Indian numbers. And from the Persians the idea came to the Arabs. In turn, the Arabs passed it to the Europeans, who called this method of recording Arabic numerals. This is the basic number system that most of the world uses today.

    The truly remarkable thing is that no matter what language you speak, you can understand these numbers. The notation of numbers is as universal as human communication.

    Number Recording and Math


    Here is the same number recorded in all the systems mentioned.

    image

    And all these systems worked. They have been used by key nations and empires for centuries. Therefore, it is difficult to say that one of these systems is better than the other.

    The only advantage the Indian system had over all the others was that it was possible to take a column of numbers and put them together without using scores - with just a pen, paper and a slightly trained brain. It was not easy to do in any other system.

    Today it doesn’t matter, because we have computers. Therefore, there is no clear answer to why we are still using this system. Perhaps there are some advantages to using it that I cannot imagine, for example, in dialing a phone number. It seems that using Roman numerals will make this rather difficult. But I don’t remember the last time I dialed a phone number. So maybe that doesn't matter anymore.

    The important idea is that Indian numbers taught us math.


    This is a positional system. You can take the numbers and put them on the number line, and then add up the numbers in each position, multiplying them by 10 to the power corresponding to the number of this position. It turns out that Indian numbers are short for polynomials. A polynomial is a really important concept in mathematics. We got a way to write numbers. This was not in other systems.

    Whole numbers


    This system also allowed negative numbers.


    We could write down a number with a minus sign by imagining negative things. This concept was meaningless in other number systems. We could not talk about the negative in Egypt, this did not make sense. But we can do it in the Indian system. And it turns out there are a lot of interesting things happening with negative numbers.

    Real numbers


    We can take a number series and continue it in the opposite direction to infinity. Using such a record, we get real numbers.


    Other number systems could also work with fractions. But these have always been special occasions. With the Indian system, we can write fractions in the same way as integers - we need only a little discipline in decimal point management.

    In the original Indian record, the position of the separator was indicated using the line above.


    But over the years, the separation character has changed.

    Different countries have their own agreements on how to write. Some cultures use a decimal point, while others use a comma. And it didn’t matter for a long time. You were in your own country and could write numbers correctly or incorrectly. But this becomes a problem when you have the Internet, because now numbers are everywhere. The number you record can be seen anywhere. And everyone will see different things - there may be confusion.


    For example, depending on where you are and how you studied, you can read the first number in the picture as 2048 or 2 and 48 thousandths. And this can be a really serious mistake, especially when it comes to finances.

    Therefore, I predict that the world will sooner or later find a way to choose one of the recording options. Because there is no value in this confusion. However, the difficulty in choosing one of the options lies in the fact that none of them is clearly the best. How will the world choose?

    I predict that you decide. And you choose a decimal point, because your programming language uses it. And all the numbers in the world ultimately go through computer programs. In the end, you just decide to simplify it.

    Base


    All the systems discussed above have a base of 10. This is how numbers were written in the Middle East and in China. They did not communicate with each other, but took the foundation 10.

    How did this happen? They just counted the fingers on both hands. And it worked.

    But there are other cultures that wrote numbers differently. For example, in America there was a number system with a base of 20. Do you know how they thought of it? I suppose this is obvious: they counted the fingers not only on their hands, but also on their feet. And that also worked. They had a developed civilization. They performed quite a lot of calculations, but used base 20.

    Some cultures used base 12. And we can still see their footprints in our world. For example, our watch has a base of 12. We still have 12 inches in feet. We learned this from the British and still cannot refuse to use such complications.

    Trade-offs: 60


    The Sumerians used base 60. Yes, and we still stick to base 60, right? We think our time and take geographical measurements. Geographic applications have to use a coordinate system based on a number system with a base of 60. This adds unnecessary complexity.

    How did the base 60 come about? I think when cities grew, they absorbed many small settlements, uniting them into large ones. At some point, they tried to unite the community that used base 10 with the community that took base 12. Surely there was some king or committee - someone had to decide how to combine them. The correct option was to use base 10. The second option was to develop with base 12. But instead, they chose the worst option possible — they used the base, which is the smallest common multiple. The reason this decision was made is because the committee could not decide which option is better. They reached a compromise, which, in their opinion, was similar to what everyone wanted. But the point is not who and what wants.

    It should be noted that committees still make such decisions every time they issue standards.

    Binary system


    A really interesting thing related to the foundation is the appearance of the binary system. We can take the Indian system and simply replace 10 with 2.


    So we can represent everything with a bit. And this was a really important step forward, because it allowed us to invent a computer.

    If we start talking about computers using the binary format, we need to remember the sign of the number. There are three ways to record and display a character:

    • The sign value (Signed magnitude representation). In this case, we simply add an extra binary bit to the number and decide in which state this bit corresponds to a positive number and in which to a negative one. And it doesn’t matter if we put this bit in front or behind (this is just a matter of convention). The disadvantage of this method is the presence of two zeros: positive and negative, which does not make sense, since zero does not have a sign.
    • The first addition (One's complement), in which we perform a bitwise no operation for a number, to make it negative. In addition to two zeros (positive and negative - as in the previous version), this representation has a transfer problem: with the usual addition of two numbers represented in this way, to get the correct result, you need to add 1 bit at the end. But otherwise it works.
    • The second addition (Two's complement), which managed to circumvent the problem of transfer. A negative N is not a bitwise negation of a positive N, but it is + 1. Besides the absence of a transfer problem, we get only one zero, which is very good. But at the same time we get an additional negative number. And this is a problem because you cannot get the absolute value of this number - instead, you will get the same negative number. This is a potential source of errors.

    Each of the options has its drawbacks, in particular, some additional numbers. I think that we should take this additional number (negative 0 or additional negative number from the second addition), and turn it into a signal that this is not a number at all. Thus, this will allow us to avoid the problem that manifests itself in Java: if we use the indexOf method to find a line in another line, and if it does not find it, Java cannot signal this. Because this stupid system can only return int, and int can only represent integers.


    To get around this problem, they came up with a dubious compromise: a return minus one. But unfortunately, if you just take the return value and put it in another formula, you may get the wrong result. If the method returned a null value, this could be detected in the downstream, and we would be less likely to get a bad calculation result.

    Types


    Let's take a closer look at the types used in our languages.

    int


    We have many languages ​​where under different names there is int32. If we add two int32 numbers, what type will the result be? The answer is int33, because as a result of addition you can get a number that is slightly larger than int32.

    Here Java is wrong. Java says it is int32.

    Another example is the multiplication of int32 by int32. What will we get as a result? It looks like int63.


    When, as a result of a normal calculation, a result is obtained that goes beyond the type, we get an overflow. And our CPUs are aware of this. For example, in Intel architecture, the CPU has a carry flag that contains this 33rd bit. Also on Intel architecture, if you do 32-bit number multiplication, you get a 64-bit result. Those. a register is provided that contains the “extra” 32 bits you need. And there is an overflow flag that is set if you want to ignore the high multiplication order. He reports that an error has occurred. Unfortunately, Java does not allow you to receive this information. She just discards everything that is a problem.

    What should happen at all when overflowing? There are several options here:

    • we can store null, which I think is very reasonable;
    • or the maximum possible part (saturation). This may be reasonable when processing signals and in computer graphics. However, you do not want to do this in financial applications;
    • an error can be thrown - the machine must throw an exception or something must happen. Software must understand that there has been confusion in the calculations and it is necessary to correct the situation;
    • some say the program should stop. This is a rather sharp reaction, but such an option would work if the car did not just stop, but somehow informed that something was wrong.

    If you intend to maximize the number of possible errors, you simply discard the most important bits without notice. This is what Java and most of our programming languages ​​do. Those. they are designed to increase the number of errors.

    Splitting numbers into values ​​from different registers


    The first computers worked with integers. But the machines were built and programmed by mathematicians, and they wanted to work with real numbers. Therefore, arithmetic was developed, where a real number is represented by an integer multiplied by some scale factor.

    If you have two numbers with the same scaling factors, you can simply add them, and if they have different scaling factors, you will have to change at least one of them to perform the simplest operations. Therefore, before performing any operations, it is necessary to compare the scale factor. And the recording became a little more complicated, because in the end you had to put an excess scale factor. And the division is complicated because you have to consider the scaling factor. As a result, people began to complain that it made programming really difficult, very error prone. In addition, it was difficult to find the optimal scale factor for any application.

    As a solution to these problems, someone suggested making floating point numbers that could display approximated real numbers using two components: the number itself and the record of where the decimal separator is inside it.

    Using such a record, addition and multiplication can be relatively easy. So you get the best results that the machine can provide, using much less programming. It was a great achievement.

    The first form of writing a floating-point number looks something like this: we have some number whose value is increased by 10 to the power of the logarithm of the scale factor.


    This approach was implemented in the software of the first machines. It worked, but extremely slowly. The machines themselves were very slow, and all these transformations only worsened the situation. Not surprisingly, there was a need to integrate this into hardware. The next generation of machines, already at the hardware level, understood floating point calculations, however, for binary numbers. The transition from decimal to binary was caused by a loss of performance due to dividing by 10 (which must sometimes be done to normalize numbers). In a binary system, instead of dividing, it was enough to simply move the delimiter - it is practically “free”.

    Here's what a binary floating-point standard looks like:


    The number is written using the mantissa sign bit, which is 0 if the number is positive, and 1 if negative, the mantissa itself, as well as the biased exponent. The offset in this case plays the role of a small optimization - due to it, you can perform an integer comparison of two floating-point values ​​to see which one is larger.

    However, there is a problem with this record: in it 0.1 + 0.2 is not equal to 0.3.


    The result is close, but it is wrong.

    Let's see what happens.


    Imagine a number series. 0.1 is about 1/16 + 1/32, but a bit more, so we need a few more bits. As we move through the number series, we get the endlessly repeating series 0011, similar to what happens with 1/3 in decimal.


    This is great if you have an infinite number of bits left. If you continue this sequence to infinity, you get exactly what you need. But we do not have an infinite number of bits. At some point, we must cut off this tail. And the final error will depend on where you cut.

    If you cut before 0, you will lose all subsequent bits. Therefore, your result will be slightly less than necessary. If you cut off before 1, according to the rules of rounding, you need to transfer the unit, then the result will be a little more.


    And you can hope that during the calculations you will make a little mistake one way and the other, and as a result, the errors will be balanced. But this does not happen. Instead, the error accumulates - the more calculations we do, the worse the result.

    Whenever we represent a constant in a program written in some language or in data as a decimal fraction, we do not get exactly this number. We get an approximation of this number because we are working with a numerical system that cannot represent decimals exactly. And this violates the associative law.

    Associative law is really important during the algebraic manipulation of expressions in programs. But it is not respected if the inputs / outputs and intermediate results of the calculations cannot be accurately represented.

    And since none of our numbers are accurately represented, all calculations are wrong! This means that (A + B) + C is not the same as A + (B + C), that the order in which you perform the calculations can change the result.

    This problem is not new. She was known even when floating-point computing in the binary system developed - the developers thus compromised.

    There were two schools of computing at that time:

    • those involved in scientific work wrote in Fortran using floating-point numbers in the binary system;
    • those in the business wrote in Cobol using binary coded decimal (BCD). The binary decimal code allocates 4 bits for each number and carries out the usual calculation in decimal system (using ordinary arithmetic).


    Computers are getting cheaper, and now they are solving almost any problem, but we are still stuck in this template with two different worlds.

    Another problem with representing binary floating point numbers is the difficulty of converting text. Take a piece of text and turn it into a number; then we take the number and convert it back to a piece of text. This must be done correctly, efficiently and without surprises, using as few digits as possible. It turns out that in such a record this is a very complex problem, expensive in terms of performance.

    Type problem


    In most modern programming languages, there is confusion due to erroneous data types. For example, if you write in Java, each time creating a variable, property or parameter, you need to select the type correctly from Bite, Char, Short, Int, Long, Float, Double. And if you choose the wrong one, the program may not work. Moreover, the error will not appear immediately, and it will not be visible in the tests. It will show itself in the future when there will be overflow and the bad things connected with it.

    What can happen? One of the most impressive examples was the failure of Aryan 5. This is a rocket launched by the European Space Agency. She deviated greatly from the course, and then exploded a few seconds after the start. The reason for this was a bug in software written in Ada. Here I translated the error into Java:


    They had a variable defining horizontal displacement. And she was transferred to Short, which overflowed. The result in Short was incorrect. But he was sent to the guidance system and completely confused it, so the course could not be restored. This error is estimated at about half a billion dollars.

    I believe that you have not made mistakes that would cost half a billion dollars. But they could (technically still possible). Therefore, we should try to create recording systems and languages ​​that avoid such problems.

    Dec64


    From the point of view, choosing a data type when declaring JavaScript variables is much better - this language has only one numerical type. This means that a whole class of errors can be automatically avoided. The only problem is this type is wrong, as these are binary floating point numbers. And we need decimal floating-point numbers, because sometimes we add up money and want the result to make sense.

    I suggest fixing this type. My fix is ​​called DEC64, it is a modern notation for decimal floating point numbers. I recommend DEC64 as the only numerical type in application programming languages ​​in the future. Because if you have only one numerical type, you cannot make a mistake by choosing the wrong type (I think this will provide much more value, with something that we can get with several types).

    The hardware implementation of DEC64 allows you to add numbers in one cycle, which reduces the importance of performance when using older types. The advantage of DEC64 is that in this entry, basic operations on numbers work the way people are used to. And eliminating numerical confusion reduces errors. In addition, converting DEC64 numbers to text and vice versa is simple, efficient, and free of surprises. This is actually a bit more complicated than converting integers to text and vice versa - you just need to keep track of where the decimal point is, and you can remove the excess of zeros from both ends, not just one.

    DEC64 can accurately represent decimal fractions containing up to 16 digits, which is quite enough for most of our applications. You can represent numbers from 1 * 10 -27up to 3 with 143 zeros.

    DEC64 is very similar to the original floating-point numbers developed in the 40s. A number is represented as two numbers that are packed in a 64-bit word. The coefficient is represented by 56 bits, and the indicator is represented by 8 bits.


    The reason the exhibitor is at the end is because in Intel architecture we can unpack such a number almost for free. This helps in the implementation of the software.

    If you want to look at the software implementation of DEC64, you can find it on GitHub . And if you are thinking of developing the next programming language, I highly recommend that you consider DEC64 as the only numerical type.

    With the DEC64 format, I do not hope to get into the following JavaScript, since this is a fundamental change. Knowing how the committee works, I do not think it is possible. DEC64 will help the creator of the next programming language (I hope that JavaScript does not become the last programming language - we cannot leave it to the children; we must offer them something else).

    Uncertainties and Zeros


    = Let's get back to the numbers.

    What is 0/0?

    • Most mathematicians will say that this value is undefined, implying that it is stupid to do so - such an expression does not make sense (JavaScript defines this as Undefined ). Such a position is good for mathematics, because everything happens there in theoretical space. But this does not work for calculations, because if someone can submit this data to the input of the machine, it must somehow react (you cannot say that the design of the machine is not defined - something must happen).
    • Another theory says that a car should catch fire because no one in their right mind would try to divide 0 by 0, so this should never happen. But we know that this is not true. Because if something can happen, it will happen.
    • Another version - it must be null or some other concept that says that this is not a value. And that is reasonable.
    • Another school believes that the result should be zero . There are mathematicians who are confident in this, but for most business tasks, such a result does not make sense. If last month we sold 0 units of goods, and the total profit for these units was 0, what was the average profit for the goods? 0?
    • Some people say that it is 1 because N / N = 1.
    • I used to work on the mainframe, where the result was 2 . It was the machine that Seymour Crey created - the greatest computer designer in history. I entered 0/0 and got 2. I can imagine a dialogue in Control Data Corporation. Someone said: "Seymour, there is a problem with your division scheme!" "What is the problem?". “If someone divides 0 by 0, they get 2!” And Seymour says: “Listen ... There shouldn’t be such an operation. No intelligent person should ever do this. And if I turn on additional logic for this case, to determine the behavior of the machine, i.e. I’ll add another test, it will degrade performance for everyone, including smart people who don’t perform such operations. And that will make the car more expensive. I’m not going to do this just because some idiot wants to divide 0 by 0. "

    Also I'm interested in what is 0 * n for any value of n.

    I think this is 0. But there were compilers that, if they met in multiplication 0, did not do the multiplication at all. This was a big plus for speed. Unfortunately, when the standard for writing floating point numbers was created, this approach was declared erroneous, because if n is NaN, then the result 0 x NaN is not equal to zero.

    Why should we care about this at all?

    Such a code is written by few people, as well as many machines: code generators, macroprocessors, automation tools - they will all write code, it may well multiply something by zero.

    Modern processors have very long instruction decoding protocols that take many cycles. But they can quickly process many instructions until there are no conditional jumps. If there is a conditional transition, everything stops until it is clear which way to move on. And it really slows down. There is a way to write code when, instead of choosing between two values ​​(conditions), an additional action is performed - multiplying by 0 or 1, which are the result of a logical operation (of the same condition). Although this is additional work, its execution may be faster than the execution of code with conditional branching. Therefore, I recommend that all operations with 0 (division, multiplication, division with remainder) be equal to zero.

    Like DEC64, this idea was proposed for the next generation of applied programming languages.

    Instead of a conclusion


    There are people whom I really want to thank.


    I want to start with Leonardo Fibonacci from Pisa. At the end of the XII century, Leonardo visited Arabia and learned the amazing things that Arab mathematicians embodied through their number system - algebra, geometry, algorithms. He brought them to Europe and wrote a book that he published in 1202. Over the next century, this book transformed Europe. He created the basis for new forms of banking, which led to an increase in capital that fuels the Renaissance.


    I want to thank Gottfried Wilhelm Leibniz for excellent calculations, as well as for the binary system. He was the first to understand that it is possible to put base 2 in the Indian positional number system. He thought it was wonderful. And he was right.


    I want to thank George Bull, an English logician who developed an algebra based on only two values ​​- true and false. The Boolean data type is named after him.


    I want to thank Claude Shannon, an American researcher. He did two amazing things: firstly, he found a correspondence between electronics and Boolean algebra so that we could convert Boolean algebra into circuits. This is how computers are created. Secondly, he created the theory of information, which states that any analog signal can be converted into digital and vice versa with any desired degree of accuracy. This statement underlies the Internet and all digital media: videos, audio, etc. All of them are possible thanks to the work of Shannon.


    And finally, I want to thank Teghuti. I could not find his photo, I have only this image, which was carved on the stone.

    Teghuti invented the letter. He lived in Egypt and understood the Rebus principle - that you can take an image of something, put a certain sound in accordance with this image and continue to use these images to record harmonies that could not be represented by pictures. This principle gave rise to writing.

    Teghuti was an accountant, inventor and teacher. He taught his writing system and created the profession of scribes. When the mythology of Egypt was written, its compilers inserted Teghuti into history. They elevated him to the rank of the god of writing and magic. He became a very important figure in history.

    Why would they do that? I think for two reasons. First, they wanted to show how important the scribe's position is. They put the chief scribe at the level of a god, and other gods came to him for help. And secondly, they wanted to thank him for giving them the best jobs in Egypt. They did not engage in agriculture and did not pull out stones, did not perform other heavy work.

    We are the children of Teghuti. We use a programming language to translate numbers into magic.



    If you liked this report by Douglas Crockford, we invite you to two of his new speeches at the upcoming HolyJS 2017 Moscow conference , which will be held in Moscow on December 10 and 11.