Thursday, August 14, 2008

Counting to a Billion:

In 1964, I wrote many programs for an IBM 7094 mainframe. This was a wonderful machine. It could hold 160,000 characters in its memory, although some of that memory was reserved for hold a small operating system. It could add two numbers together in just over one microsecond. We made that 7094 leap and dance in many different ways.

In those days, you submitted your programming "job" as a deck of punched cards. Some hours later, your card deck, and the computer output, appeared in an "output bin." There was one bin for every letter of the alphabet, because a lot of people submitted jobs to that one mainframe. Operators ran the decks through the computer as fast as they could. Some jobs, of course, took longer than others.

One day my wife and I were talking about counting up to large numbers. One way a growing child discovers mortality is through the realization that in one's entire life, there are numbers you cannot count up to. Counting "one, two, three, four, etc., ... one billion" is right out. That's when I noted that our 7094 could count to a billion in less than an hour. Wow!

Pretty soon we decided to do it. The only drawback was that computer time for the entire university was precious, so I did not want anyone to know what I was doing. If the computer sat in a tight loop adding one to a running total for a thousand seconds, I would probably be caught and banished from the engineering center. So I wrote a program that ran for less than two minutes. The program read in a punch card to tell it what number to start counting from, and it punched a card at the end of the run to use as input to the next run. I submitted my program once or twice a day, and proudly saved all the outputs for years.

After a few few days of these runs -- we might have been up to 403,682 or so -- Tony, the head operator, took me aside.
"You've got a funny program that sits there for two minutes and seems to do nothing. Are you sure it doesn't have a bug?"
"I'll take a look at it," I said, thankful I hadn't quite been busted. I knew I had to change the program so that it looked busy. The problem was that it sat in a tight "add one" loop, so the program counter LED display on the computer console did not change, and the other displays that showed computer activity did not change either.

I modified the program. I made it hundreds of instructions long -- most of them "add one" instructions. But among the adds, I sprinkled computer instructions to make all of the console lights turn on and off. My modified program escaped criticism, and it actually counted faster. The 7094 had "lookahead logic", and it was able to process about 1.5 of my addition instructions at once. (The simpler program, in its three instruction loop, prevented any "lookahead" from occurring.)

So: we counted to a billion. Pretty neat!


Anonymous said...

It is pretty funny that the lookahead sped things up by 50%, today most compilers will optimize counting loops to their resulting value thus the entire set of additions is reduced to one load instruction. Makes it a bit harder to actually count! said...

I would have told the compiler to turn optimizing off. You'realways allowed to do that, in case the compiler is a idjit.
- PB