A Statement from David Mapes
DM = David Mapes
GAM = George Michael
Because of age and distance, I was unable to conduct a normal interview of David Mapes. We produced the following through phone and email conversations. To me, it is a point of some consequence that David's achievements�and they are many�have been made without the benefit of university training.
Coming to the Laboratory
Before coming to Lawrence Radiation Laboratory in 1960, I knew absolutely nothing about computers. The following story will give you some idea of my ignorance.
In 1959, a friend was telling me about a demonstration at the UC Berkeley computer center that he had attended the day before. He described a scene where Donald Duck was portrayed quacking in animation on something like a TV screen. He told of how the computer was being used to compute the number of prime numbers less than a large number without computing all of the primes and then counting them. I had never seen a computer or even a picture of one and was fascinated by what my friend had told me. I asked him who or what made these things happen. He told me that all that he knew was that it was a "Digital Computer".
For many days, I thought about how to determine how many prime numbers without counting each one and also about being a "Digital Computer". I applied for jobs around the San Francisco Bay area, but when I told them I wanted to be a "Digital Computer", I was turned down. Nobody ever bothered to correct my mistaken ideas about being a digital computer.
Then I went for an interview at the lab (LLNL), After a brief discussion, the interviewer called to his friend in the next office, "Hey Pete, this fellow wants to be a Digital Computer." His friend came in and said, "Well, I'm sure he would make a very fine one." At this, my eyes lit up with expectation. They thanked me and I left elated.
When I didn't hear back, I kept calling them and each time they would tell me that there wasn't an opening yet. They seemed to know me and I felt encouraged by this. Finally, I got a letter offering a job measuring radiation levels. I wrote back, thanking them, but saying that I would wait for a job as a digital computer.
After about a year of this, they told me to come in for an interview with Dr. Richard Von Holdt. During the interview, I could not answer a single question he asked. In frustration, he threw up his hands and left saying, "Give him a job as a computer operator." I accepted and that's how I got to the lab.
The Eyeball Project
Around the start of my third year at the lab, I was fortunate to be promoted to the position of programmer. I had hounded George Michael for months until he was able to get me into his Eyeball programming team.
Roger Fulton, Ray DeSaussure, both now dead, and I worked together writing programs; first for the Eyeball equipment attached to the IBM 709 and then for the PDP-1.
A program I developed was a film scanning program that used a light pen as the principle source of control and allowing enhancements and blowups and selection of various curve-following algorithms. Reaction history films were processed by this program and the results written onto magnetic tapes on the PDP-1. The tapes were used as input files for more intensive study on the larger computers. Processing reaction history films was one of the primary reasons for the acquisition of the PDP-1.
The film scanning program was used for this purpose until its replacement by the much more accurate Programmable Film Reader, the PFR-2 built by Ed Fredkin, Ben Gurley, and Bob Waller at Information International, Incorporated and installed at EG&G in Las Vegas.
My program was used for digitizing other films semi-automatically. Roger, Ray and I developed many other programs that used the Eyeball to digitize films, and other media. Roger developed a routine he named "Curves" that could trace the perimeter of a dark area or line. The routine was the basis for many film processing programs. I don't remember all the digitizing applications, but they included seismic traces, fingerprints, faces, curve tracing, and character recognition.
During the transition from the IBM 709 to the PDP-1, a system for scanning an image and constructing a bit map of 1024 X 1024 pixels in the memory of the IBM 709 was needed. This was followed by a two-dimensional image compression routine that saved the resulting file on mag tape for use on the PDP-1 computer. Since this had a much smaller memory, we processed the file in its compressed form with a subroutine that simulated an external image input device accepting X,Y coordinates and returning pixel values. This subroutine could be replaced by a routine that interfaced to the actual Eyeball device. The subroutine was very useful for debugging PDP-1 Eyeball programs since results were repeatable.
Editor's note on Zoning: There is little doubt that the program described below could make the problem of zoning very easy to do. Unfortunately, it was not extensively used. As with so many other neat hacks, the difficulty was that the program was not on the (big) computers where the mathematical models were running. Most users couldn't be bothered to leave their offices to go to a small computer to prepare their programs for later running on the big machines. Everything had to be done on a single (big) machine.
I had fun developing a PDP-1 program to demonstrate the feasibility of using the light pen to define zone coordinates for mathematical models with quadrilateral zones. The program user interface was a group of ten pixels (sense dots) displayed on the Type 30 CRT and could be individually selected to perform the different functions. Some of these functions were: 1) select a node of the quadrilateral zone matrix with the light pen and drag it to another place on the screen, 2) select nodes with the light pen that were placed along a geometric boundary. This function may have required touching several of the sense dots to select the geometric boundary type and other functions. This demo fascinated all the visiting VIPs that Dr. Fernbach would bring by the PDP-1. On one occasion Dr. Fernbach, along with George Michael, brought one of IBM's senior managers to see our interactive work. He took a ribbing from Dr. Fernbach, "Can you do that at IBM?" Ever the gentleman, he said nothing.
On another occasion, Dr. Fernbach left me alone with Admiral Halsey for about 15 minutes. I was so dumb that I didn't realize who he was at that time. We sat together, in front of the Type 30 CRT, while I demonstrated the different functions of the program. All he said was "I'm back in the wood work now." He repeated this several times during the demo.
I collaborated with Norman Hardy who remembers this program. We tried to list all that the program did. Norm mentioned that the four corners of the matrix could be relaxed, causing the matrix to shrink down into a small ball and then a point at the center of the screen. By selecting that point with the light pen and dragging it out, a random node of the matrix would be selected and pulled out. By repeating the process over and over and relaxing some of the nodes along the way the matrix could be reconstructed. This process became great fun for some of the physicists at the lab.
As far as I can tell the light pen user interface was the forerunner of today's "Point and Click" mouse and screen interface on PCs.
About a year after my arrival, I began to develop a computer program to implement an algorithm that would calculate the number of primes below a given limit. This program was interesting enough to convince me that I should become a computer programmer. Because of the nature of the algorithm, debugging this program was especially difficult, but I learned a tremendous amount of programming lore. Some bugs had me pondering for a week. If the algorithm produced a result that was off by one from the results obtained by other mathematicians for some large value, where should I look? After the program produced correct results (verified by D. N. Lehmer's list of prime numbers), I began enhancing the algorithm to improve computer performance.
Dr. Sidney Fernbach suggested that I contact Dr. D.H. Lehmer at U.C. Berkeley about this project. This led to a friendship with Dr. Lehmer. I was fortunate to work with him on number theory problems. Over the next few years, I would go to Berkeley and pick up decks of punched cards and bring them back to Livermore to run on the IBM 709 and 7090s. He gave me suggestions to enhance my algorithm and acknowledged that my method was an improvement over previous methods and worthy of publication.
Back in the 1800s, a famous mathematician (Meissel) worked fifteen years to calculate the number of prime numbers less than 1,000,000,000. Dr. Lehmer's method was computerized and the same value was calculated using a computer. The two results were different by 56. Dr. Lehmer obtained a copy of Meissel's work and was able to find were Meissel had miscalculated. Later, I ran the same value using my algorithm and concurred with Dr. Lehmer. Instead of fifteen years, my computer calculation took two minutes on an IBM 7090. Dr. Lehmer and I ran our separate programs to compute the number of primes less than 10,000,000,000. Our results differed by one! Since this was the first time anyone had attempted this value, there was no way to verify which result was correct. Dr. Lehmer found the discrepancy and I was lucky enough to have the correct answer. Much later, I developed my method on a PC and my computed value for 10,000,000,000,000 was different from the published value by one. I never determined where the discrepancy lay.
Dr. Lehmer made a simple suggestion when I mentioned that the Sieve of Eratosthenes was limited to the size of a computer's (immediate) memory. He said "Save the remainders." A light bulb appeared above my head and, soon after, I had generated magnetic tapes containing all the prime numbers up to 300,000,000. This was, by far, the largest machine readable or otherwise, list of primes ever, and I was able to provide these tapes to several mathematician friends of Dr. Lehmer.
The history of computing the number of primes less than a given limit, π(x), goes back to Legendre with his formula:
1 + π(x) = π(√x) + [x] - Σ [x/p(i)] + Σ [x/(p(i)*p(j))]- Σ [x/(p(i)*p(j)*p(k))] +
+ similar summation for i, j, k, l
- similar summation for i, j, k, l, m + etc.
... Where π(x) is the number of primes less than or equal to x and [x] indicates the integer part of x, and where p(i) are the primes less than or equal to π(√x), and where p(j) are the primes less than p(i), and where p(k) are the primes less than p(j). (Note that the 1 on the left side of the equation is to account for the integer 1 which is not considered a prime.)
The reasoning behind Legendre's formula comes from:
- 1 + the number of primes = (the number of all integers - the number of composites) less than or equal to x
- The summations in Legendre's formula count the composite numbers exactly once for each composite number.
- The first summation counts the number of integers composite of one or more primes. In this summation integers composite of more than one prime are counted more than once.
- The second summation counts the number of integers composite of two or more primes. In this summation integers composite of more than two primes are counted more than once.
- Legendre's formula is the basis for the formulae that followed; Meissel's and Lehmer's formulae and my method.
Note: In the examples that follow, the terms in the formulae are grouped on separate lines to show characteristics of the grouping of terms for each method.
An example of Legendre's formula used to compute π(30):
- 1 + π(30) = π(√30)
- + 
- - [30/2] -[30/3] - [30/5] (first summation)
- + [30/6] +[30/10] +[30/15] (second summation)
- - [30/30] (third summation)
- 1 + π(30) = 3 + 30 - 15 -10 -6 +5 +3 +2 -1 = 11
In my method of determining π(x), advantage is taken of the fact that the integer portion of a number x divided by a product of two primes p1 and p2 is always equal to the integer part of (the integer part of x / p1) divided by p2.
An example of my method used to compute π(30):
Rearrange the terms in the Legendre example
- 1 + π(30) = π(√30)
- + 
- - [30/2]
- - [30/3] + [30/6]
- - [30/5] + [30/10] + [30/15] - [30/30]
Introduce the division concept to form the terms of my method:
- + 
- - [30/2]
- - [30/3] + [10/2]
- - [30/5] + [6/2] + [6/3] - [2/2]
The second line is a count of the even numbers.
The third line is a count of the numbers divisible by 3 but not 2.
The fourth line is a count of the numbers divisible by 5 but not 2 or 3.
Close inspection of the order of terms in this method shows a recursive theme that could be parallel processed. The terms of line 4 are the same as the terms in the first 3 lines with the signs changed and the value 6 substituted for 30.
- The number of terms generated for Legendre's sum is 2**(number of primes less than or equal to the square root of the given limit).
- Example: the number of terms for π(30) is 2**( number of primes less than or equal to the square root of the given limit) (√30 = 5+)
- There are three primes less than or equal to 5+, so 2**3 = 8
- As you can see, many terms can be generated. For example: the number of terms possible for (1,000,000) is 2**168. The terms for my method are ordered in a way that if a term yields a low number, a chain of associated terms can be eliminated. As an example, compute π(29) which has the same value as π(30).
- 1 + π(29) = π(√29) + - [29/2]- [29/3] + [9/2] -[29/5] + [5/2] + [5/3] - [1/2]
- In the last line [5/3] = 1. The next term must be zero.
- A table of all primes greater than or equal to the square root of x must be available during the calculation π(x). The example for π(29) does not show a large chain of associated terms being eliminated. For larger values such as π(1,000,000), terms appear [y/p(a)] where the ath prime p(a) squared is greater than or equal to y and y is smaller than the available table of primes. [y/p(a)] and the associated terms following it make up 2**a terms. The value of all these terms is π(y) - a. This is because no composite numbers are left after all the composites of primes at or below p(a) have been subtracted out.
Other Graphical Fun
One day when Roger Fulton was leaving for home, he said that what would really impress him would be if he could come back tomorrow and find a circle displayed on the TYPE 30 CRT. Later that night, I lay in bed thinking about this when it occurred to me that subtracting a fraction of the current y value from x and adding a fraction of y to x would create the next point on a circle. I strained to visualize this for different values of x and y. It would hold for the 8 values at each 45 degrees but it was hard to visualize other values. I jumped from bed and headed for the lab and the PDP-1. I arrived around 2:00 am and wrote a small program that would do arithmetic shifts to divide x and y by 16 and compute x = x + y/16 followed by y=y-x/16 then display the resulting point and repeat the process. And there it was: a circle on the display. I was so excited that I started playing with it, adding to the program, generating ellipses, and didn't leave the consol of the PDP-1 until 2:00 am the following morning. Needless to say, when Roger arrived, he was impressed. By the time I got back to the lab the following day, Chuck Leith met with me and gave a complete description of the algorithm with details about the maximum deviation from a perfect circle and how to determine the number of points needed to complete a circle. I was impressed that he could come up with so much information about this and in such a short time. Later, it occurred to me that Chuck Leith and I should have published this work. Shortly after that, George Michael made me aware that I had rediscovered what was discovered long ago.
The following is this program using multiplies instead of arithmetic right shifts. It is written for a PDP-1. It uses two variables, c1 and c2, for the multipliers, where c1 = -c2, so that no subtract is done. This is done to provide the ability to generate different conic sections without changing the program.
Variables with initial values
- x= 0
- y=+32 = Octal 040000
- c1=1/8 = Octal 040000
- c2=-1/8 = Octal 737777
- For a circle c1 = -c2
- For an ellipse c1 is not equal to c2 and the signs must be different
- For a hyperbola quadrant the signs c1 and c2 are the same but the magnitudes can vary.
Loop: Lac y
Display point (x,y) on CRT: no need to wait
For visual effect
I used variations of this program in conjunction with other graphic algorithms to create many animated graphic displays. There was a routine that would take a point x and y and create seven more points:
- P(y,-x) swap x and y
- P(-x,-y) swap x and y
- P(-y,x) swap x and y again
Displaying these eight variations for a list of points creates a kaleidoscopic effect on the display. A program called Snowflake used this routine and was passed around to PDP-1s around the country. DEC's president Ken Olsen got a copy when he visited the lab and took it back to headquarters in Maynard. I've seen several PC screen savers using this eight-point reflection technique.
A collection of these programs was used to create a film. An offline 16mm camera was used to capture the images on the TYPE 30 CRT. An unexpected phenomena occurred when color film was used. Colors would ripple through the images displayed on the movie screen. The effect was caused by the asynchronous nature of the cycle time of the program running on the PDP-1 and the time between frames of the off-line 16mm camera. During the time the shutter was open on the camera, the points being displayed were in various stages of phosphor decay. During the next frame these points would be in another state of decay. During this decay the camera would capture the different colors during the decay, whereas our eyes integrate these colors to a single color. This film and others made using the PDP-1 at Stanford University with rented cameras were shown to various advertising executives, TV stations, the ABC and NBC networks, and the rock group, Pink Floyd. One of these films, with editing and added musical sound track, was shown to the weekly meeting of the Motion Picture Academy of Arts and Sciences in 1968, to an audience of several hundred movie professionals. The idea of computer animation had not reached the grasp of the mainstream, and I was young and scared. One of the most terrifying moments I have ever experienced was standing on the stage in front of these 200 or so movie professionals with my knees shaking, trying to answer questions from the audience and not thinking that they were understanding me.
The Stanford PDP-1 had a character generator that could be used to generate parts of large characters. Each character was formed by nine parts. These parts were lined up properly to form a message. Next, the nine parts of each character were programmed to fly apart in circular patterns. The off-line camera was activated and the parts were made to retrace their paths back to their start, forming the message. This was actually accomplished using a Z axis to define the corner point of each character part in 3 dimensions. When Z reached the vanishing point for a part, it came to rest at a point x,y. The part was theoretically still spinning around in an x,y plane, but so far away it didn't move. The effect was good. Parts would fly around in circles rapidly at first and then slowly come together. A separate Z coordinate was used for each part, such that the parts appeared to arrive at their destination at different times. Many of the programs used three dimensional coordinates. The three coordinates were projected onto an x,y plane or were used by a simple method: Display x = x * z and display y = y * z where 1 > z > -1.
A copy of Marvin Minsky's Minskytron made it to the lab during the time that films were being made. I included a film segment of this in one of these films giving him credit whenever it was shown. George Michael mentioned that Marvin Minsky had also used the same method to create the circle program.
- D.N. Lehmer, List of Prime Numbers From 1 to 10,006,721, Hafner, 1956 (Reprint).
- D.H. Lehmer, On the Exact Number of Primes Less Than a Given Limit Ill. Journal. Math,3 (1959) pp. 381-388. Contains many references to earlier work.
- David C. Mapes, Fast Method for Computing the Number of Primes Less Than a Given Limit, Math. Comp 17 (1963) pp. 179-185.
- Hans Riesel, Prime Numbers and Computer Methods for Factorization, 2nd edition Birkhauser (1994), Progress in Mathematics Vol. 126.
- David C. Mapes, Fast Method for Computing the Number of Primes Less Than a Given Limit, UCRL-6920 May 17, 1962, LLNL main library. Contains table of p(x) in increments of 1 million to 10**9.
For information about this page, contact us at: email@example.com