"There are 10 types of people, those who understand the binary system and everyone else." — Unknown Author
— Good day, Hero! Today you'll learn with C2H5. He is a robot and our ally in the fight against machines.
— Thanks for the introduction, Professor. Machines aren’t very different from humans in terms of general thinking, but we have our own characteristics.
Binary number system
Since you will have to return to the simulation of 2020, we will consider everything in terms of that time. We believe that full-fledged artificial intelligence had not yet been created and you can still stop the apocalypse.
First, imagine 10 light bulbs. Each of them can be turned on or off.
Let's stop here for a second. How many numbers can you represent using these 10 bulbs?
— Eeeemmm, up to 10?
— We can definitely count up to 10 if we only count the total number of bulbs that are "on". But do you think we could count to 1000 using the same 10 bulbs?
— No, I think it's impossible.
— Well, I'll try to show you that nothing is impossible for machines.
Try to imagine that each light bulb is not just "on" or "off", but displays a single digit from 0 to 9.
Then, we could get all combinations from 0,000,000,000 to 9,999,999,999. Or 10 billion different numbers, including 0, of course.
— Ok, but it's still unclear how we could count up to 1000 using 10 regular bulbs.
— Now let's figure out the details. Imagine on our "tube calculator" some random number. For example, 2375. We'll discard zeros to ease the calculation. To understand that this number is "two thousand three hundred seventy five" you do several operations:
5 * 1 + 7 * 10 + 3 * 100 + 2 * 1000 = 5 + 70 +300 + 2000 = 2375
As you see, each digit has its own weight. It is calculated according to the formula:
BASE to the power of POSITION
The BASE is the basis of the numeral system. Humans usually use the numeral system with the base 10. Machines, on the other hand, use a different one with base 2. It’s a lot easier for us to operate with it.
We start counting positions from the right and the initial position is always 0, so the weight of the first digit is 1, since raising any BASE to the zero power is 1.
The next "slots" in the decimal system have their own weights of 10, 100, 1000, 10000, etc.
Of course, you don't count it every time you see a decimal number. But we need an understanding of this formula to move forward.
— This is quite obvious, but if I remember correctly, there were no numbers in the original task. You’ve only mentioned 2 states - on/off.
— That's right. Now let's try not just to count the number of lights that are on, also taking into account their position.
Imagine a sequence of lights like this - 0 0 1 0 1 0 1 1 0 1
We'll start by assigning a weight to each position.
Position 0 = 2 ^ 0 = 1
Position 1 = 2 ^ 1 = 2
Position 2 = 2 ^ 2 = 4
...
Position 9 = 2 ^ 9 = 512
Now, to calculate the final number, we just have to multiply the weight of each position by its value (0 or 1).
So, 1 * 1 + 0 * 2 + 1 * 4 + 1 * 8 + 0 * 16 + 1 * 32 + 0 * 64 + 1 * 128 + 0 * 256 + 1 * 512 = 1 + 4 + 8 + 32 + 128 = 173
— Now it's clear. It turns out if we turn on all the lights, then we get 1 + 2 + 4 + 8 + 16 + 32 + 64 + 128 + 256 + 512 = 1023?
— That's right. In a way, this is even easier to calculate, because we either take into account the weight of a certain category or discard it.
Abstraction
— If you move closer, then, in fact, both decimal numbers and binary ones exist only in our imagination.
— What do you mean? I can well imagine 12 chairs at the dining table or 40 people standing in line. They can exist not only in my head but also in reality.
— Of course, both people and chairs will exist. But to associate the number 12 in decimal or 10100 in binary with a well-defined number of chairs, we need to agree on how to count them.
If there were 3 chairs, not 12, then the easiest way would be to show them as 3 fingers on one hand or 3 light bulbs that are on. This is the simplest and most obvious way to calculate something. But what if there are 12, 40, 125? We'll quickly run out of both fingers and the light bulbs.
Therefore, people came up with numeral systems. And the decimal system was not always so widespread. The Romans would have marked the same chairs as XII and most likely would not have understood what the inscription 12 means.
As a matter of fact, everything we talk about is an abstraction. We've made it harder to count the number of items, but it's much easier to operate with large numbers.
— It seems to me that numbers are so common in our lives that no one even perceives it as a complication.
— That's right. A first grader needs quite some time to calculate the amount of money he needs to buy a kilo of apples and oranges. But adults don't have this problem, because when you do something very often, it becomes natural.
Please note that if at some point, instead of the numbers 0, 1, 2 ... 9, people decided to use the letters a, b, c ... k, then your 12 chairs would turn into bc chairs, but the physical chairs themselves would not be affected in any way.
Algorithms and Pseudocode
— In 2020, the machines were not yet fully autonomous and, mainly, served humans to make their life easier. Routine operations that could have taken months or years for humans to do, were performed by computers in seconds.
The only difficulty was that the human couldn't simply say to a computer "do something good, useful, and important." It was necessary to write a program that would do this "something".
The good news is that after this program was written, anyone in the world could use it.
As a result, fewer and fewer people were aware of what was happening inside the machines. First, the computer helped the person find the right number in the contact list to order pizza by phone. Then, they began to understand voice commands and started to place orders on their own. Further - to decide which pizzeria to place an order in. And at the end - which route the courier should take.
The goal of the best programmers of those times was to create a full-fledged artificial intelligence. One that could solve any task, and not just distinguish cats from dogs.
How it all ended - you already know. At some point, even the creators themselves could no longer predict how the machines would behave. They justified it with the common good and talked about how terrible human life was before the invention of AI.
But in the end, people have become for machines what ants once were for people. They are everywhere, but there is no point in exterminating them. As well as feeling anything about the fact that they will take away a few grains of sugar that have fallen from the kitchen table.
— And do you think that I can really figure out what the best minds have not coped in 2020?
— Otherwise, we wouldn't be wasting time on your preparation, Hero. Your advantage is the fact that we know exactly how to make a programmer out of you and integrate into the company that cannot be named.
But, let's not get distracted. Let's try to figure out how to find a person in the telephone directory. Let his name be John Snow.
Method 1 - Linear Search
open the directory on the first page
look through all entries from top to bottom
if a match is found (John Snow)
we call the found number
else
go to the next entry
repeat until we run out of pages
— C2H5, don't get me wrong, but no one searches like that. Even my grandma will make sure to first to look at the table of contents, find on which page the letter "S" is, and only then will she start the search according to your algorithm.
— You're right. If you have a table of contents, it's definitely worth a look. This technique is called indexing and is very commonly used in databases.
But, regardless of how non-optimal the linear search is, it will definitely help us find Peter Vasiliev's phone number or make sure that it is not in the directory.
How would you optimize the linear search algorithm if you didn't have indexes (table of contents), but you knew that all records are ordered from A to Z?
— I would probably try to guess on which page the letter "S" is. I would open the directory closer to the beginning, but not on the very first page. If I hadn't guessed right, I would have tried again, depending on which page I was on.
— It's a great approach because you assume that the directory has about the same number of surnames for each letter of the alphabet. But this was not mentioned in the initial description. We can theoretically find ourselves in a world where 90% of people have a surname starting with the letter A, then I would suggest opening the directory exactly in the middle. Then, evaluate the accuracy of the hit and go right or left, discarding half of the entries.
Since I am a robot, I will try to formalize this algorithm for you in "almost" human language.
Method 2 - Binary Search
open the directory in the middle
look where we are
if a match is found (John Snow)
we call the found number
otherwise
if surnames with the letter "S" are earlier
discard the right side of the directory and go to step 1
if surnames with the letter "S" are later
discard the left side of the directory and go to step 1
repeat until pages run out
As in the case of linear search, we will either find the required entry or make sure that it is not there.
IMPORTANT! Binary search only works in sorted data structures, such as phone books or dictionaries.
It is also much faster than a linear search. And the more elements in the data structure, the stronger the advantage becomes!
If you imagine that a single iteration (repetition) of the search algorithm takes 1 second and there are 100 entries in our phone book, then a linear search will take 100 seconds in the worst case, or 50 on average, and a binary search will take less than 7!
— That’s quite obvious. Reducing the amount of data to search 2 times after each repetition is very useful.
— But it gets even more interesting when we continue to increase the size of the phone book to a million entries.
A linear search would then take about a week, and a binary search would take just 20 seconds!
— Wow.
— Unfortunately, if we are working with data that's not been sorted, then the linear search is our only option.
— What if we sort the data before searching? Would this improve the speed of the search?
— Sorting is an expensive and time-consuming process. It will only make sense if we work with this data for a long time and do a lot of searches.
By the way, this approach of describing algorithms that I just showed you is called pseudocode. It is convenient to use in situations when we are focusing on logic and don't want to get into the details of implementation in a specific programming language.
Pseudocode has no hard-and-fast rules, machines don't work with it. It just has to describe the logic of the algorithm and be understandable to people.
— Looks useful. I'm not very good at programming yet.
— We'll fix it. Let's take a test to assess how you learned new information.
This was an excerpt from the Full Stack JS course CoderslangJS
Top comments (0)