Donald Knuth 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 instruction manual was pretty dumb. It pushed me to programming. ”



How am I interested in computers? I had a scholarship to study at the Keysov Institute of Technology, but it did not cover the full cost of training, but only part, and therefore I had to get a part-time job. My parents did not have money, and I went to work for the Department of Statistics. One of my responsibilities was to manage the sorting machine, the IBM mechanical machine for sorting punch cards, and that was pretty fun. It was necessary to take punch cards and place them in the machine, which sent them to different pockets, then get the punch cards in a certain order and then check the results and draw the graphs. So, I drew charts for the Department of Statistics.

Translation: Julia Khaitova Publication
Support - Edison, which develops geolocation games with orcs and demons and CRM systems to coordinate the work of branches .

My interest in graphs and my first experience of a computer

I think I have something else to add about the graphs before the thought escapes. In high school, I spent the whole summer on ... I was passionate about graphs in mathematics, you know, there is an argument x and a function y, and you need to draw a graph that is y unit segments higher than the axis, actually the graph of the function is obtained. From that moment I like the visuals.

I was very keen on the idea that I could start with the image that I would like to get in the end, and pick up an equation whose graph would allow it to be done. So, I spent the summer sorting out graphing. I drew hundreds and hundreds of graphs at a time. As an equation, I could take, for example, the square root of x ^ 3 + 5x minus some other number, and plotted its graph.

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

I didn’t have mathematical analysis at school, I just didn’t find out, but I was able to plot equations graphs. This enthralled me. I worked so hard on this, built graphs on orange graph paper, it even made my head hurt. I think that around this time I started wearing glasses, all because of the schedules. 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 graphs for statisticians. It was great, and not far from the sorting machine there was a new computer, or, as it was called “artificial intelligence”, the IBM Model 650.

This was the first mass-produced computer model: more than 1000 were produced. Well, before that, computers were not produced in batches, in which there would be 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 a room, on the floor below the office in which I worked. I could even see the computer through the office window.

One day, an employee noticed me looking 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 computer that my father showed me, so I decided to get acquainted with the instruction manual.

He soon allowed me to punch holes on punch cards that were designed for a computer. You see, I knew how to control the sorting machine, but at that moment I was making punch cards with computer programs. And so I began to find out about what is inside this device.

How I got interested in programming

I read the IBM instruction manual and it contained examples of programs, and I thought about how I could 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 would most likely not even be interested in writing programs, because I would not be so confident in myself and, frightened, just waved away: “Oh, I would never have thought of such a thing ". But the bottom line is that this instruction manual was pretty dumb. It pushed me to programming, because, say, I could succeed in this.

So I began to be interested in computers during the first year of my studies at the institute. And then, when I joined the fraternity, one of the participants had a problem with a task that he had to urgently solve: find the root of an equation of degree 5. I already knew about a program called “Bell Interpretive System”, which could easily solve his problem, because he, you know, didn’t want to do it on his own.

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

And somewhere between the first and second year I worked part-time 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: factorization of 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 it finally worked correctly, it had 130, I think that I corrected about 200 errors during this time.

I mean, I learned not only programming, but also error correction. What can go wrong when you just ... Well, I didn’t know much about programming then, but I learned a lot from this practice, writing a program to calculate 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 the binary system, but in decimal; and in the end, even ten-digit numbers could be obtained. 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 working millions of times faster. By today's standards, it was an incredibly slow computer that didn't even have the ability to produce multiple division processes at the same time.

And finding the factors was as follows: first, to divide this number into two is not suitable. On three? Not. At four? Not. And so on until it works out. Now you can quite simply pick up the largest ten-digit prime number, and then it took a lot of time, so you had to at least slightly speed up the program.

I should not have divided first by two, then by three, four, five, but I could have skipped all the even numbers if the original 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 by 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 have approximately the same value. That’s how I realized that I need to slightly modify the algorithm in the program.

One of the most implicit errors in the program, which took me a lot of time to fix, was that the number suddenly has a lot of prime factors? As it turned out, I could break through only 9 factors on a punch card, I had to redo the program, because numbers can have more than 30 factors. And I changed it so that now the answers made their way not on one map, but on four.

And yet, it was ... I just want to explain why this multiplier program was so useful to me at that time. And after all, I wrote it at the end of the first year, I was allowed to spend nights sitting at this apparatus, 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 IBM employees who needed to hand over the work so that they could pass it directly through the machine, so it was possible to get the results only the next day.

At the Keysov Institute, it was allowed to do everything on their own, they didn’t even worry that we could break something, but we opened the panels when paper or cards got 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 to use the technology on their own.

Writing a tic-tac-toe program

In the summer, I worked at the Computer Center, so I was not at home in Milwaukee, except for only a couple of days. And that was before I met those second year girls that I already spoke about. So, I spent the whole summer with a computer. My second program was the conversion from decimal to other number systems, but it was pretty fast. The third program, on 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 to play Tic Tac Toe in the 1800s. Danny Hillis made a Tic-Tac-Toe slot machine from the Tinkertoys children's designer, 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 the decimal system, with 10-digit numbers, but it only had 2000; his general memory was, let’s 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 had only 10 KB of shared memory.

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

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

It was hardly possible to fit this into 10KB. Each time when losing during the game, she said something like: “I made a mistake, the opponent’s moves were good”, and when I won: “My moves were good, but the opponent’s moves didn’t.” She could adjust.

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

It took me a month to write this program ... I learned a lot during this time, and after that I tried to teach the "training version" of the game using the "expert" version. How many times did the “expert” play with the “training version”? I think about 120, and then the "training version" stopped losing 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 carries away. 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 quite conservatively, the games became boring. Instead of making deliberate and risky moves, they played very carefully. Nevertheless, writing this program has become a rewarding experience.

Read more

• Donald Knuth: I sat on the back desks and bullied jokes, and the teachers humbled themselves and didn’t beat their asses often (1,2,3,7 / 97)
  
• Donald Knuth: “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 Knuth: How The Art of Programming Was Created (33.38.39 / 97)
  
• Donald Knuth: When will the fourth volume finally be released
• Donald Knuth: How I spent the summer with a computer, not with girls (19,20,21,22 / 97)