Apollo Guidance Computer fixed-point arithmetic
Introduction to the Apollo Guidance Computer
Apollo Guidance Computer was a digital computer produced for the Apollo program. The command module flies to the moon orbit. The lunar module then descends to the moon and makes way back to the command module.
The Virtual AGC was a project started in 2003 by volunteers and took about 20 years to restore the software line by line into digital form. The amount of effort invovled was beyond description. One may clone the repository with all the code and documents:
git clone https://github.com/virtualagc/virtualagc.git
The Colossus software runs on the command module and the Luminary software runs on the lunar module. There is another significant Abort Guidance System as a backup computer system, made by a different company, different team of people, only using common hardware technology then.
The design principles developed for the AGC by MIT Instrumentation Laboratory, directed in late 1960s by Charles Draper, became foundational to software engineering—particularly for the design of more reliable systems that relied on asynchronous software, priority scheduling, testing, and human-in-the-loop decision capability.
The processing logic runs at roughly the same speed as the access to memory. The clock that drives internal operations is at 1.024MHz. It takes 12 cycles to read from and write back to memory: 12 / (1.024*10^6/s) = about 11 microseconds. An assembly instruction takes one to several times of 11 microseconds to execute.
The basic unit of storage is 15-bit, called a word. One word is single-precision. Two words are double-precision. Multiplication of two single-precision integers would yield a double-precision integer.
An interpreter is also implemented. The interpreter language can simulate a stack, do high-precision arithmetic and vector operations, essential to navigation math.
The operating system is real-time, consisting of one co-operative scheduler and one interrupt-driven pre-emptive scheduler. The pre-emptive scheduler famously cleaned out low priority routines from memory when the processing logic was too busy.
Fixed-point arithmetic
The Apollo Guidance Computer only does integer multiplication and division. So how were trigonometric functions computed, essential to space flight, which usually require real numbers?
It makes approximation with polynomials as does Taylor series expansion.
For precise approximation formulas, search for documents entitled “Guidance Equations” in the AGC Document Library for various Apollo flights.
As a prelude to the next section, we introduce the fixed-point arithmetic. Note in the decimal system, two integers
3 x 5 = 15
At the same time, two fractional numbers
0.3 x 0.5 = 3 / 10 * 5 / 10 = 15 / 100 = 0.15
So in order to computer the multiplication of two fractional numbers with the same number of digits after the decimal point, we can take the fractional parts, do the arithmetic as with integers, and finally put the decimal point at the beginning of the integer result.
Double-precision multiplication
How does it calculate any item in the above polynomial? would be a fractional number. The programmer has to remember the decimal point is before the fractional part. The fractional part is stored as one or more 15-bit integers.
Below we illustrate with the code of Luminary099, the version that flew Apollo 11 the first man-landing mission. The routine is DMPSUB called by POLY for polynomial valuation. Go to https://www.ibiblio.org/apollo/Luminary.html, in the version table find “Apollo 11”, version “099/1”, click on the “syntax-highlighted, hyperlinked HTML”. On the page for the version 099, scroll down, locate the symbol DMPSUB in the SymbolTable, and click on it.
DMPSUB multiplies two double-precision fractional numbers and keeps the most significant three words as result. The programmer has to treat the result as a fractional number, with a decimal point before all the words.
Denote the two multiplicants as x, y. The fractional part of x is stored in two words x_major and x_minor, likewise is y. Just as the multi-digit multiplication we learnt in primary school, we multiply different word pairs from the two multiplicants and sum over the intermediate results.
x_major x_minor
y_major y_minor
--------------------------------------
x_minor x y_minor
x_major x y_minor zeros
y_major x x_minor zeros
x_major x y_major zeros zeros
In the code below, ADDRWD+0 is x_major, ADDRWD+1 is x_minor. MPAC+0 is y_major, MPAC+1 is y_minor. The result will be stored in MPAC, MPAC+1, MPAC+2, discarding the least significant word.
On the Apollo Guidance Computer, there is one register A as accumulator, storing current temporary result. Multiplication MP would place the more significant part of result in register A, and the less significant part in register L.
Refer to the code for the original comment. The comment below is added for this blog post.
DMPSUB INDEX ADDRWD
CA 1 # load ADDRWD+1 or x_minor into register A
TS MPAC +2 # store register A to MPAC+2, x_minor at MPAC+2 now
CAF ZERO # zero in A
XCH MPAC +1 # exchange register A with MPAC+1, y_minor into A, zero into MPAC+1
TS MPTEMP # store register A to MPTEMP, y_minor at MPTEMP now
EXTEND
MP MPAC +2 # multiply register A with MPAC+2, i.e. y_minor with x_minor
XCH MPAC +2 # the most signficant part of result in A, after exchanging, MPAC+2 holds the most significant part of the result, A holds x_minor
EXTEND
MP MPAC # multiply register A with MPAC, i.e. x_minor with y_major
DAS MPAC +1 # add the two-word result to MPAC+1 and MPAC+2
INDEX ADDRWD
CA 0 # x_major in register A
XCH MPTEMP # exchange register A with MPTEMP, y_minor in A, x_major in MPTEMP
DMPSUB2 EXTEND
MP MPTEMP # multiply register A with MPTEMP, i.e. y_minor with x_major
DAS MPAC +1 # add the two-word result to MPAC+1 and MPAC+2
XCH MPAC # exchange register A with MPAC+0, y_major in A, 0, 1 or -1 in MPAC
EXTEND
MP MPTEMP # multiply register A with MPTEMP, i.e. y_major with x_major
DAS MPAC # add the two-word results to MPAC and MPAC+1
TC Q # transfer control to the return address in register Q
If one clicks on the ADDRWD, MPAC in the original code, one will be redirected to their declarations in the erasable memory assignment file. Their addresses are fixed (no dynamic allocation of memory) but the content in them can change.
For more detail on each instruction and their effect, consult the Assembly Language Manual and the discussion at https://github.com/virtualagc/virtualagc/discussions/1262.
References
Apollo Guidance Computer, https://en.wikipedia.org/wiki/Apollo_Guidance_Computer
Luminary software for the Lunar Module, https://ibiblio.org/apollo/Luminary.html
Virtual AGC Assembly-Language Manual, https://ibiblio.org/apollo/assembly_language_manual.html
Virtual AGC Document Library, https://www.ibiblio.org/apollo/links.html
Eldon C. Hall (1996). Journey to the Moon: The History of the Apollo Guidance Computer
Hidden Figures, 2016 film.
Michael Steil, Christian Hessmann, the ultimate Apollo Guidance Computer talk, https://media.ccc.de/v/34c3-9064-the_ultimate_apollo_guidance_computer_talk
Steve Baines, the curious design of the Apollo Guidance Computer, https://media.ccc.de/v/emf2022-105-the-curious-design-of-the-apollo-guidance-computer
Charles Averill, a brief analysis of the Apollo Guidance Computer, https://arxiv.org/abs/2201.08230
Mike Kohn, Apollo Guidance Computer in an FPGA, https://www.mikekohn.net/micro/apollo11_fpga.php