Donald Knut on the first steps in programming: How I spent the summer with a computer, not with girls (19,20,21,22 / 97)

“The bottom line is that this IBM Model 650 operating manual was pretty dumb. It pushed me to programming. ”



How did I become interested in computers? I had a scholarship to study at the Keysov Institute of Technology, but it did not cover the full cost of education, but only a part, and therefore I had to get a part-time job. My parents had no money, and I went to work at the Department of Statistics. One of my responsibilities was managing a sorting machine, an IBM mechanical punch card sorting machine, and it was pretty exciting. It was necessary to take punched cards and put them in a machine that sent them to different pockets, then take out punched cards in a certain order and then check the results and draw graphs. So, I drew charts for the Department of Statistics.
')
Translation: Julia Khaitova
Publication support is Edison , which develops geolocation games with orcs and demons and CRM systems for coordinating branch operations .

My computer experience

I think I should add something else about the charts before the thought escaped me. In high school, I spent the whole summer on ... I was fascinated with graphs in mathematics, you know, there is an argument x and a function y, and you need to draw a graph that is on y single segments higher than the axis, the graph of the function itself turns out. From that moment on, I like visual images.

I was very passionate about the idea that I could start with an image that I would like to get in the end, and pick up an equation whose schedule would allow it. So, I spent the summer trying to figure it out. I drew hundreds and hundreds of graphs at that time. As an equation, I could take, for example, the square root of x ^ 3 + 5x minus some other number, and plotted it.

My father had a small counting machine on which I could calculate the roots. She even printed the result. My father was an accountant, so the machine even printed out the result. I used it for multiplication and other arithmetic operations. Then, let's say, I changed x ^ 3 + 5x to x ^ 3 + 4x and was already drawing a new graph, remembering how different graphs look.

I did not have a mathematical analysis at school, I simply did not recognize it, but I could build graphs of equations. It delighted me. I worked so hard on it, built graphs on orange graph paper, it even made my head ache. I think that at about this time I started wearing glasses, all because of the graphs. But I got at least some experience in construction, and I liked this section of mathematics, even when I was in high school.

And then I got my first part-time job at the Keysov Institute of Technology, where I had to draw charts for statisticians. It was great, and not far from the sorting machine was a new computer or, as it was then called “artificial intelligence,” IBM Model 650.

It was the first model of a mass-produced computer: more than 1000 of them were released. Well, before that, computers were not produced in batches with more than 30 copies. And when this computer was brought, it was in the middle of my first year of study at the institute, it was installed in the room, on the floor below the office in which I worked. I could even see the computer through the cabinet window.

One day, a worker noticed me peeking at a computer and invited me in. He explained to me how this device works. I was impressed, because this computer could do so many things, unlike the calculating machine my father showed me, so I decided to familiarize myself with the operating manual.

Soon he allowed me to punch holes on punch cards that were meant for a computer. You see, I knew how to operate a sorting machine, but at that moment I was making punch cards with computer programs. And so I began to learn about what is inside this device.

How I got interested in programming

I read the IBM manual, and it contained examples of programs, and I thought about how to improve the process of writing programs. I thought, "Well, yes, these programs work, but if you change something, it will become even better." This gave me confidence that maybe I have a talent for programming.

If, then, the manual did not have those unsuccessful examples, I, most likely, would not even be interested in writing programs, because I would not be so sure of myself and, frightened, just waved away: “Oh, I would never have thought of such ". But the bottom line is that this operating manual was pretty dumb. It also pushed me to programming, because I, say, could succeed in this.

So I became interested in computers during my first year at the institute. And then, when I joined the fraternity, one of the participants had a problem with the task, which he had to urgently solve: to find the root of the equation of the 5th degree. At that time I already knew about the program called “Bell Interpretive System”, which could easily solve his problem, since he did not want to do it himself, you know.

So, I wrote a program for my “brother” who would do one of his assignments for him. And the program worked. It was hard for me to believe it, but it was so. And he was so happy about it. In addition, I began to communicate more with people from the Computer Center when they began to allow me to use this IBM machine at night.

And somewhere between the first and second year I was working at the Computer Center. They actually allowed us to write software that other people — other students — would use.

The first computer program I wrote was as follows: decomposing a number into prime factors. Enter the number through the console, namely the rotary switch, which could be moved to a number, for example, 100, and then the following data was output: 100 = 2 * 2 * 5 * 5. So it was possible to calculate the prime factors of the number that was entered through the console.

I still have a copy of this program of mine. Initially, it all started with about 60 or 70 teams in the program, and after 2 weeks, when she finally earned correctly, there were 130 in it, I think that I corrected about 200 errors during this time.

I mean that I studied not only programming, but also error correction. What can go wrong when you just ... Well, I didn't really know much about programming back then, but I learned a lot from this practice, writing a program for calculating prime factors of a number.

Learning how to program on the ibm 650

I also understood some things, for example, there was a decimal computer that worked not in binary calculus, but in decimal; and in the end could even get ten-digit numbers. I was able to learn how to use such a computer, although it was very, very slow.

The division process took him about 4 milliseconds, while now computers are running millions of times faster. By today's standards, it was an incredibly slow computer that didn’t even have the ability to perform multiple division processes at the same time.

And finding the multipliers happened as follows: first, divide this number by two or no match. On three? Not. By four? Not. And so on until it works out. Now you can quite simply select the largest ten-digit prime number, and then it took a lot of time, so you had to speed up the program a little.

I shouldn’t have to divide by two, then by three, four, five, I could skip all the even numbers if the initial number is not divisible by 2 and 4. And I had to do this kind of thing to speed up the process. At first, I did not understand that I did not need to divide into all possible numbers, because if a number has factors at all, then the smallest factor will be less than the square root of this number or approximately equal in value. This is how I realized that I need to change the algorithm a little in the program.

One of the most implicit errors in the program that took me a lot of time to correct was that all of a sudden there are a lot of simple factors in the number? As it turned out, I could only punch 9 multipliers on a punched card, I had to redo the program, because numbers can have more than 30 multipliers. And I changed it so that now the answers were punched not on one card, but on four.

And yet, it was ... I just want to explain why this multiplier program was so helpful to me at that time. And I did write it at the end of the first year, I was allowed to spend the night sitting behind this device, switching levers, pressing buttons, and after all, the Keysovsky Technological Institute allows students to practice. Teachers allowed us to use computers on our own, work at night, fall asleep in classrooms and write programs that other students would use.

At Stanford University everything was different. At Stanford, as I later found out, there were employees from IBM who had to take the work so that they could pass it directly through the device, so it was possible to get results only the next day.

At the Keysov Institute, it was allowed to do everything independently, they didn’t even worry that we could break something, but we opened the panels when paper or cards were stuck and all that. And we were only freshmen! I think that Case and Dartmouth were the only universities in those days that were so liberal with their students and allowed themselves to use the technology.

Writing a tic-tac-toe program

In the summer I worked at the Computer Center, so I was not at home in Milwaukee, except perhaps for a couple of days. And that was before I met those girls in the second year that I already talked about. So, I spent the whole summer with a computer. My second program was to convert from the decimal system to other number systems, but it was pretty fast. The third program, over which I spent more time, was the game Tic-tac-toe.

Later I learned that many scientists worked on this game. Charles Babbage, an English mathematician who invented the first machine that could play Tic-Tac-Toe in the 1800s. Danny Hillis made the Tic-Tac-Toe game machine from the children's designer Tinkertoys, which is now on display at the Boston Museum of Science. Nevertheless, I decided that I would write a computer program for this game. it was quite problematic.

I did not use Tinkertoys, but the IBM 650 had another interesting feature: it worked not only in decimal system, with 10-digit numbers, but it had only 2000; his general memory was, let me think how much? 5 bytes? So, only 10 KB of memory. And now if you do not have 10 GB, or at least 10 MB, then this is the end. You can’t even download Microsoft Windows if you don’t have hundreds of MB, and then we only had 10 KB of shared memory.

And I wanted the car to play tic-tac-toe against me. And I wrote three levels of difficulty. The first level is “expert”, with a strategy I was sure of.

What was the second? I don’t remember, but the third one was the most interesting. It was a “learning version”: the car started the game without knowing anything, and she herself learned during the game, memorized all possible positions on the field.

It was hardly possible to fit this into 10 Kb. Every time she lost during the game, she said something like: “I made a mistake, the opponent’s moves were good,” and when she won, “My moves were good, and the opponent’s moves were not.” She could adapt.

Each difficulty level corresponded to a certain number, the game could start at 4, and if you won, then the next one would be 5, and if you lost, then 3. And if you started using different strategies, then she picked up those moves that seemed most appropriate.

It took me a month to write this program ... I learned a lot during this time, and after that I tried to teach the "learning version" of the game using the "expert" version. How many times did the “expert” play with the “learning version”? I think about 120, and then the “learning version” stopped playing to the “expert”.

Tic-tac-toe is a rather boring game, because you know how to play it and each game ended in a draw: no one won - no one lost. But when you are mistaken - it is fascinating. And I decided that I would create two “learning versions” and they would play with each other: at first they would not know anything about the game, and their first moves would be made at random, blindly.

Of course, they will make mistake after mistake, but in the end one of them will win, and some will lose, and their strategy will change a little. And as I found out, after the games played, they began to play rather conservatively, the games became boring. Instead of making deliberate and risky moves, they played very carefully. And yet, writing this program has become a rewarding experience.

Read more

• Donald Knut: I sat in the back row and hunted jokes, and the teachers resigned and didn't often beat on the ass (1,2,3,7 / 97)
  
• Donald Knut: “My advice to the young” (93/97) and “Feeling the need to assert oneself” (9/97)
  
• Surreal Numbers: I worked for six days, and rested on the seventh (40,41,42 / 97)
  
• Donald Knut: How the “Art of Programming” was created (33,38,39 / 97)
  
• Donald Knut: When will the fourth volume finally come out?
• Donald Knut: How I spent the summer with the computer, not with the girls (19,20,21,22 / 97)