Intel released the powerful Pentium processor in 1993, establishing a long-running brand of processors. Earlier, I wrote about the ROM in the Pentium's floating point unit that holds constants such as π. In this post, I'll look at some interesting circuits associated with this ROM. In particular, the circuitry is implemented in BiCMOS, a process that combines bipolar transistors with standard CMOS logic. The photo below shows the Pentium's thumbnail-sized silicon die under a microscope. I've labeled the main functional blocks; the floating point unit is in the lower right with the constant ROM highlighted at the bottom. The various parts of the floating point unit form horizontal stripes. Data buses run vertically through the floating point unit, moving values around the unit. Die photo of the Intel Pentium processor with the floating point constant ROM highlighted in red. Click this image (or any other) for a larger version. The diagram below shows how the circuitry in this post forms part of the Pentium. Zooming in to the bottom of the chip shows the constant ROM, holding 86-bit words: at the left, the exponent section provides 18 bits. At the right, the wider significand section provides 68 bits. Below that, the diagram zooms in on the subject of this article: one of the 86 identical multiplexer/driver circuits that provides the output from the ROM. As you can see, this circuit is a microscopic speck in the chip. Zooming in on the constant ROM's driver circuits at the top of the ROM. The layers In this section, I'll show how the Pentium is constructed from layers. The bottom layer of the chip consists of transistors fabricated on the silicon die. Regions of silicon are doped with impurities to change the electrical properties; these regions appear pinkish in the photo below, compared to the grayish undoped silicon. Thin polysilicon wiring is formed on top of the silicon. Where a polysilicon line crosses doped silicon, a transistor is formed; the polysilicon creates the transistor's gate. Most of these transistors are NMOS and PMOS transistors, but there is a bipolar transistor near the upper right, the large box-like structure. The dark circles are contacts, regions where the metal layer above is connected to the polysilicon or silicon to wire the circuits together. The polysilicon and silicon layers form the Pentium's transistors. This photo shows part of the complete circuit. The Pentium has three layers of metal wiring. The photo below shows the bottom layer, called M1. For the most part, this layer of metal connects the transistors into various circuits, providing wiring over a short distance. The photos in this section show the same region of the chip, so you can match up features between the photos. For instance, the contacts below (black circles) match the black circles above, showing how this metal layer connects to the silicon and polysilicon circuits. You can see some of the silicon and polysilicon in this image, but most of it is hidden by the metal. The Pentium's M1 metal layer is the bottom metal layer. The M2 metal layer (below) sits above the M1 wiring. In this part of the chip, the M2 wires are horizontal. The thicker lines are power and ground. (Because they are thicker, they have lower resistance and can provide the necessary current to the underlying circuitry.) The thinner lines are control signals. The floating point unit is structured so functional blocks are horizontal, while data is transmitted vertically. Thus, a horizontal wire can supply a control signal to all the bits in a functional block. The Pentium's M2 layer. The M3 layer is the top metal layer in the Pentium. It is thicker, so it is better suited for the chip's main power and ground lines as well as long-distance bus wiring. In the photo below, the wide line on the left provides power, while the wide line on the right provides ground. The power and ground are distributed through wiring in the M2 and M1 layers until they are connected to the underlying transistors. At the top of the photo, vertical bus lines are visible; these extend for long distances through the floating point unit. Notice the slightly longer line, fourth from the right. This line provides one bit of data from the ROM, provided by the circuitry described below. The dot near the bottom is a via, connecting this line to a short wire in M2, connected to a wire in M1, connected to the silicon of the output transistors. The Pentium's M3 metal layer. Lower layers are visible, but blurry due to the insulating oxide layers. The circuits for the ROM's output The simplified schematic below shows the circuit that I reverse-engineered. This circuit is repeated 86 times, once for each bit in the ROM's word. You might expect the ROM to provide a single 86-bit word. However, to make the layout work better, the ROM provides eight words in parallel. Thus, the circuitry must select one of the eight words with a multiplexer. In particular, each of the 86 circuits has an 8-to-1 multiplexer to select one bit out of the eight. This bit is then stored in a latch. Finally, a high-current driver amplifies the signal so it can be sent through a bus, traveling to a destination halfway across the floating point unit. A high-level schematic of the circuit. I'll provide a quick review of MOS transistors before I explain the circuitry in detail. CMOS circuitry uses two types of transistors—PMOS and NMOS—which are similar but also opposites. A PMOS transistor is turned on by a low signal on the gate, while an NMOS transistor is turned on by a high signal on the gate; the PMOS symbol has an inversion bubble on the gate. A PMOS transistor works best when pulling its output high, while an NMOS transistor works best when pulling its output low. CMOS circuitry normally uses the two types of MOS transistors in a Complementary fashion to implement logic gates, working together. What makes the circuits below interesting is that they often use NMOS and PMOS transistors independently. The symbol for a PMOS transistor and an NMOS transistor. The detailed schematic below shows the circuitry at the transistor and inverter level. I'll go through each of the components in the remainder of this post. A detailed schematic of the circuit. Click for a larger version. The ROM is constructed as a grid: at each grid point, the ROM can have a transistor for a 0 bit, or no transistor for a 1 bit. Thus, the data is represented by the transistor pattern. The ROM holds 304 constants so there are 304 potential transistors associated with each bit of the output word. These transistors are organized in a 38×8 grid. To select a word from the ROM, a select line activates one group of eight potential transistors. Each transistor is connected to ground, so the transistor (if present) will pull the associated line low, for a 0 bit. Note that the ROM itself consists of only NMOS transistors, making it half the size of a truly CMOS implementation. For more information on the structure and contents of the ROM, see my earlier article. The ROM grid and multiplexer. A ROM transistor can pull a line low for a 0 bit, but how does the line get pulled high for a 1 bit? This is accomplished by a precharge transistor on each line. Before a read from the ROM, the precharge transistors are all activated, pulling the lines high. If a ROM transistor is present on the line, the line will next be pulled low, but otherwise it will remain high due to the capacitance on the line. Next, the multiplexer above selects one of the 8 lines, depending on which word is being accessed. The multiplexer consists of eight transistors. One transistor is activated by a select line, allowing the ROM's signal to pass through. The other seven transistors are in the off state, blocking those ROM signals. Thus, the multiplexer selects one of the 8 bits from the ROM. The circuit below is the "keeper." As explained above, each ROM line is charged high before reading the ROM. However, this charge can fade away. The job of the keeper is to keep the multiplexer's output high until it is pulled low. This is implemented by an inverter connected to a PMOS transistor. If the signal on the line is high, the PMOS transistor will turn on, pulling the line high. (Note that a PMOS transistor is turned on by a low signal, thus the inverter.) If the ROM pulls the line low, the transistor will turn off and stop pulling the line high. This transistor is very weak, so it is easily overpowered by the signal from the ROM. The transistor on the left ensures that the line is high at the start of the cycle. The keeper circuit. The diagram below shows the transistors for the keeper. The two transistors on the left implement a standard CMOS inverter. On the right, note the weak transistor that holds the line high. You might notice that the weak transistor looks larger and wonder why that makes the transistor weak rather than strong. The explanation is that the transistor is large in the "wrong" dimension. The current capacity of an MOS transistor is proportional to the width/length ratio of its gate. (Width is usually the long dimension and length is usually the skinny dimension.) The weak transistor's length is much larger than the other transistors, so the W/L ratio is smaller and the transistor is weaker. (You can think of the transistor's gate as a bridge between its two sides. A wide bridge with many lanes lets lots of traffic through. However, a long, single-lane bridge will slow down the traffic.) The silicon implementation of the keeper. Next, we come to the latch, which remembers the value read from the ROM. This latch will read its input when the load signal is high. When the load signal goes low, the latch will hold its value. Conceptually, the latch is implemented with the circuit below. A multiplexer selects the lower input when the load signal is active, passing the latch input through to the (inverted) output. But when the load signal goes low, the multiplexer will select the top input, which is feedback of the value in the latch. This signal will cycle through the inverters and the multiplexer, holding the value until a new value is loaded. The inverters are required because the multiplexer itself doesn't provide any amplification; the signal would rapidly die out if not amplified by the inverters. The implementation of the latch. The multiplexer is implemented with two CMOS switches, one to select each multiplexer input. Each switch is a pair of PMOS and NMOS transistors that turn on together, allowing a signal to pass through. (See the bottom two transistors below.)1 The upper circuit is trickier. Conceptually, it is an inverter feeding into the multiplexer's CMOS switch. However, the order is switched so the switch feeds into the inverter. The result is not-exactly-a-switch and not-exactly-an-inverter, but the result is the same. You can also view it as an inverter with power and ground that gets cut off when not selected. I suspect this implementation uses slightly less power than the straightforward implementation. The detailed schematic of the latch. The most unusual circuit is the BiCMOS driver. By adding a few extra processing steps to the regular CMOS manufacturing process, bipolar (NPN and PNP) transistors can be created. The Pentium extensively used BiCMOS circuits since they reduced signal delays by up to 35%. Intel also used BiCMOS for the Pentium Pro, Pentium II, Pentium III, and Xeon processors. However, as chip voltages dropped, the benefit from bipolar transistors dropped too and BiCMOS was eventually abandoned. The BiCMOS driver circuit. In the Pentium, BiCMOS drivers are used when signals must travel a long distance across the chip. (In this case, the ROM output travels about halfway up the floating point unit.) These long wires have a lot of capacitance so a high-current driver circuit is needed and the NPN transistor provides extra "oomph." The diagram below shows how the driver is implemented. The NPN transistor is the large boxy structure in the upper right. When the base (B) is pulled high, current flows from the collector (C), pulling the emitter (E) high and thus rapidly pulling the output high. The remainder of the circuit consists of three inverters, each composed of PMOS and NMOS transistors. When a polysilicon line crosses doped silicon, it creates a transistor gate, so each crossing corresponds to a transistor. The inverters use multiple transistors in parallel to provide more current; the transistor sources and/or drains overlap to make the circuitry more compact. This diagram shows the silicon and polysilicon for the driver circuit. One interesting thing about this circuit is that each inverter is carefully designed to provide the desired current, with a different current for a high output versus a low output. The first transistor (purple boxes) has two PMOS transistors and two NMOS transistors, so it is a regular inverter, balanced for high and low outputs. (This inverter is conceptually part of the latch.) The second inverter (yellow boxes) has three large PMOS transistors and one smaller NMOS transistor, so it has more ability to pull the output high than low. This transistor turns on the NPN transistor by providing a high signal to the base, so it needs more current in the high state. The third inverter (green boxes) has one weak PMOS transistor and seven NMOS transistors, so it can pull its output low strongly, but can barely pull its output high. This transistor pulls the ROM output line low, so it needs enough current to drive the entire bus line. But this transistor doesn't need to pull the output high—that's the job of the NPN transistor—so the PMOS transistor can be weak. The construction of the weak transistor is similar to the keeper's weak transistor; its gate length is much larger than the other transistors, so it provides less current. Conclusions The diagram below shows how the functional blocks are arranged in the complete circuit, from the ROM at the bottom to the output at the top. The floating point unit is constructed with a constant width for each bit—38.5 µm—so the circuitry is designed to fit into this width. The layout of this circuitry was hand-optimized to fit as tightly as possible, In comparison, much of the Pentium's circuitry was arranged by software using a standard-cell approach, which is much easier to design but not as dense. Since each bit in the floating point unit is repeated many times, hand-optimization paid off here. The silicon and polysilicon of the circuit, showing the functional blocks. This circuit contains 47 transistors. Since it is duplicated once for each bit, it has 4042 transistors in total, a tiny fraction of the Pentium's 3.1 million transistors. In comparison, the MOS 6502 processor has about 3500-4500 transistors, depending on how you count. In other words, the circuit to select a word from the Pentium's ROM is about as complex as the entire 6502 processor. This illustrates the dramatic growth in processor complexity described by Moore's law. I plan to write more about the Pentium so follow me on Bluesky (@righto.com) or RSS for updates. (I'm no longer on Twitter.) You might enjoy reading about the Pentium Navajo rug. Notes The 8-to-1 multiplexer and the latch's multiplexer use different switch implementations: the first is built from NMOS transistors while the second is built from paired PMOS and NMOS transistors. The reason is that NMOS transistors are better at pulling signals slow, while PMOS transistors are better at pulling signals high. Combining the transistors creates a switch that passes low and high signals efficiently, which is useful in the latch. The 8-to-1 multiplexer, however, only needs to pull signals low (due to the precharging), so the NMOS-only multiplexer works in this role. (Note that early NMOS processors like the 6502 and 8086 built multiplexers and pass-transistor logic out of solely NMOS. This illustrates that you can use NMOS-only switches with both logic levels, but performance is better if you add PMOS transistors.) ↩

The cargo cult metaphor is commonly used by programmers. This metaphor was popularized by Richard Feynman's "cargo cult science" talk with a vivid description of South Seas cargo cults. However, this metaphor has three major problems. First, the pop-culture depiction of cargo cults is inaccurate and fictionalized, as I'll show. Second, the metaphor is overused and has contradictory meanings making it a lazy insult. Finally, cargo cults are portrayed as an amusing story of native misunderstanding but the background is much darker: cargo cults are a reaction to decades of oppression of Melanesian islanders and the destruction of their culture. For these reasons, the cargo cult metaphor is best avoided. Members of the John Frum cargo cult, marching with bamboo "rifles". Photo adapted from The Open Encyclopedia of Anthropology, (CC BY-NC 4.0). In this post, I'll describe some cargo cults from 1919 to the present. These cargo cults are completely different from the description of cargo cults you usually find on the internet, which I'll call the "pop-culture cargo cult." Cargo cults are extremely diverse, to the extent that anthropologists disagree on the cause, definition, or even if the term has value. I'll show that many of the popular views of cargo cults come from a 1962 "shockumentary" called Mondo Cane. Moreover, most online photos of cargo cults are fake. Feynman and Cargo Cult Science The cargo cult metaphor in science started with Professor Richard Feynman's well-known 1974 commencement address at Caltech.1 This speech, titled "Cargo Cult Science", was expanded into a chapter in his best-selling 1985 book "Surely You're Joking, Mr. Feynman". He said: Richard Feynman giving the 1974 commencement address at Caltech. Photo from Wikimedia Commons. But the standard anthropological definition of "cargo cult" is entirely different: 2 An anthropology encyclopedia gives a similar definition: As you may see, the pop-culture explanation of a cargo cult and the anthropological definition are completely different, apart from the presence of "cargo" of some sort. Have anthropologists buried cargo cults under layers of theory? Are they even discussing the same thing? My conclusion, after researching many primary sources, is that the anthropological description accurately describes the wide variety of cargo cults. The pop-culture cargo cult description, however, takes features of some cargo cults (the occasional runway) and combines this with movie scenes to yield an inaccurate and fictionalized dscription. It may be hard to believe that the description of cargo cults that you see on the internet is mostly wrong, but in the remainder of this article, I will explain this in detail. Background on Melanesia Cargo cults occur in a specific region of the South Pacific called Melanesia. I'll give a brief (oversimplified) description of Melanesia to provide important background. The Pacific Ocean islands are divided into three cultural areas: Polynesia, Micronesia, and Melanesia. Polynesia is the best known, including Hawaii, New Zealand, and Samoa. Micronesia, in the northwest, consists of thousands of small islands, of which Guam is the largest; the name "Micronesia" is Greek for "small island". Melanesia, the relevant area for this article, is a group of islands between Micronesia and Australia, including Fiji, Vanuatu, Solomon Islands, and New Guinea. (New Guinea is the world's second-largest island; confusingly, the country of Papua New Guinea occupies the eastern half of the island, while the western half is part of Indonesia.) Major cultural areas of Oceania. Image by https://commons.wikimedia.org/wiki/File:Pacific_Culture_Areas.jpg. The inhabitants of Melanesia typically lived in small villages of under 200 people, isolated by mountainous geography. They had a simple, subsistence economy, living off cultivated root vegetables, pigs, and hunting. People tended their own garden, without specialization into particular tasks. The people of Melanesia are dark-skinned, which will be important ("Melanesia" and "melanin" have the same root). Technologically, the Melanesians used stone, wood, and shell tools, without knowledge of metallurgy or even weaving. The Melanesian cultures were generally violent3 with everpresent tribal warfare and cannibalism.4 Due to the geographic separation of tribes, New Guinea became the most linguistically diverse country in the world, with over 800 distinct languages. Pidgin English was often the only way for tribes to communicate, and is now one of the official languages of New Guinea. This language, called Tok Pisin (i.e. "talk pidgin"), is now the most common language in Papua New Guinea, spoken by over two-thirds of the population.5 For the Melanesians, religion was a matter of ritual, rather than a moral framework. It is said that "to the Melanesian, a religion is above all a technology: it is the knowledge of how to bring the community into the correct relation, by rites and spells, with the divinities and spirit-beings and cosmic forces that can make or mar man's this-worldly wealth and well-being." This is important since, as will be seen, the Melanesians expected that the correct ritual would result in the arrival of cargo. Catholic and Protestant missionaries converted the inhabitants to Christianity, largely wiping out traditional religious practices and customs; Melanesia is now over 95% Christian. Christianity played a large role in cargo cults, as will be shown below. European explorers first reached Melanesia in the 1500s, followed by colonization.6 By the end of the 1800s, control of the island of New Guinea was divided among Germany, Britain, and the Netherlands. Britain passed responsibility to Australia in 1906 and Australia gained the German part of New Guinea in World War I. As for the islands of Vanuatu, the British and French colonized them (under the name New Hebrides) in the 18th century. The influx of Europeans was highly harmful to the Melanesians. "Native society was severely disrupted by war, by catastrophic epidemics of European diseases, by the introduction of alcohol, by the devastation of generations of warfare, and by the depredations of the labour recruiters."8 People were kidnapped and forced to work as laborers in other countries, a practice called blackbirding. Prime agricultural land was taken by planters to raise crops such as coconuts for export, with natives coerced into working for the planters.9 Up until 1919, employers were free to flog the natives for disobedience; afterward, flogging was technically forbidden but still took place. Colonial administrators jailed natives who stepped out of line.7 Cargo cults before World War II While the pop-culture cargo cults explains them as a reaction to World War II, cargo cults started years earlier. One anthropologist stated, "Cargo cults long preceded [World War II], continued to occur during the war, and have continued to the present." The first writings about cargo cult behavior date back to 1919, when it was called the "Vailala Madness":10 The 1926 book In Unknown New Guinea also describes the Vialala Madness:11 The Melanesians blamed the Europeans for the failure of cargo to arrive. In the 1930s, one story was that because the natives had converted to Christianity, God was sending the ancestors with cargo that was loaded on ships. However, the Europeans were going through the cargo holds and replacing the names on the crates so the cargo was fraudulently delivered to the Europeans instead of the rightful natives. The Mambu Movement occurred in 1937. Mambu, the movement's prophet, claimed that "the Whites had deceived the natives. The ancestors lived inside a volcano on Manum Island, where they worked hard making goods for their descendants: loin-cloths, socks, metal axes, bush-knives, flashlights, mirrors, red dye, etc., even plank-houses, but the scoundrelly Whites took the cargoes. Now this was to stop. The ancestors themselves would bring the goods in a large ship." To stop this movement, the Government arrested Mambu, exiled him, and imprisoned him for six months in 1938. To summarize, these early cargo cults believed that ships would bring cargo that rightfully belonged to the natives but had been stolen by the whites. The return of the cargo would be accompanied by the spirits of the ancestors. Moreover, Christianity often played a large role. A significant racial component was present, with natives driving out the whites or becoming white themselves. Cargo cults in World War II and beyond World War II caused tremendous social and economic upheavals in Melanesia. Much of Melanesia was occupied by Japan near the beginning of the war and the Japanese treated the inhabitants harshly. The American entry into the war led to heavy conflict in the area such as the arduous New Guinea campaign (1942-1945) and the Solomon Islands campaign. As the Americans and Japanese battled for control of the islands, the inhabitants were caught in the middle. Papua and New Guinea suffered over 15,000 civilian deaths, a shockingly high number for such a small region.12 map). Source: US Navy photo 80-G-41099. The impact of the Japanese occupation on cargo cults is usually ignored. One example from 1942 is a cargo belief that the Japanese soldiers were spirits of the dead, who were being sent by Jesus to liberate the people from European rule. The Japanese would bring the cargo by airplane since the Europeans were blocking the delivery of cargo by ship. This would be accompanied by storms and earthquakes, and the natives' skin would change from black to white. The natives were to build storehouses for the cargo and fill the storehouses with food for the ancestors. The leader of this movement, named Tagarab, explained that he had an iron rod that gave him messages about the future. Eventually, the Japanese shot Tagarab, bringing an end to this cargo cult.13 The largest and most enduring cargo cult is the John Frum movement, which started on the island of Tanna around 1941 and continues to the present. According to one story, a mythical person known as John Frum, master of the airplanes, would reveal himself and drive off the whites. He would provide houses, clothes, and food for the people of Tanna. The island of Tanna would flatten as the mountains filled up the valleys and everyone would have perfect health. In other areas, the followers of John Frum believed they "would receive a great quantity of goods, brought by a white steamer which would come from America." Families abandoned the Christian villages and moved to primitive shelters in the interior. They wildly spent much of their money and threw the rest into the sea. The government arrested and deported the leaders, but that failed to stop the movement. The identity of John Frum is unclear; he is sometimes said to be a white American while in other cases natives have claimed to be John Frum.14 The cargo cult of Kainantu17 arose around 1945 when a "spirit wind" caused people in the area to shiver and shake. Villages built large "cargo houses" and put stones, wood, and insect-marked leaves inside, representing European goods, rifles, and paper letters respectively. They killed pigs and anointed the objects, the house, and themselves with blood. The cargo house was to receive the visiting European spirit of the dead who would fill the house with goods. This cargo cult continued for about 5 years, diminishing as people became disillusioned by the failure of the goods to arrive. The name "Cargo Cult" was first used in print in 1945, just after the end of World War II.15 The article blamed the problems on the teachings of missionaries, with the problems "accentuated a hundredfold" by World War II. In a 1946 episode, agents of the Australian government found a group of New Guinea highlanders who believed that the arrival of the whites signaled that the end of the world was at hand. The highlanders butchered all their pigs in the expectation that "Great Pigs" would appear from the sky in three days. At this time, the residents would exchange their black skin for white skin. They created mock radio antennas of bamboo and rope to receive news of the millennium.16 The New York Times described Cargo Cults in 1948 as "the belief that a convoy of cargo ships is on its way, laden with the fruits of the modern world, to outfit the leaf huts of the natives." The occupants of the British Solomon Islands were building warehouses along the beaches to hold these goods. Natives marched into a US Army camp, presented $3000 in US money, and asked the Army to drive out the British. A 1951 paper described cargo cults: "The insistence that a 'cargo' of European goods is to be sent by the ancestors or deceased spirits; this may or may not be part of a general reaction against Europeans, with an overtly expressed desire to be free from alien domination. Usually the underlying theme is a belief that all trade goods were sent by ancestors or spirits as gifts for their descendants, but have been misappropriated on the way by Europeans."17 In 1959, The New York Times wrote about cargo cults: "Rare Disease and Strange Cult Disturb New Guinea Territory; Fatal Laughing Sickness Is Under Study by Medical Experts—Prophets Stir Delusions of Food Arrivals". The article states that "large native groups had been infected with the idea that they could expect the arrival of spirit ships carrying large supplies of food. In false anticipation of the arrival of the 'cargoes', 5000 to 7000 native have been known to consume their entire food reserve and create a famine." As for "laughing sickness", this is now known to be a prion disease transmitted by eating human brains. In some communities, this disease, also called Kuru, caused 50% of all deaths. A detailed 1959 article in Scientific American, "Cargo Cults", described many different cargo cults.16 It lists various features of cargo cults, such as the return of the dead, skin color switching from black to white, threats against white rule, and belief in a coming messiah. The article finds a central theme in cargo cults: "The world is about to end in a terrible cataclysm. Thereafter God, the ancestors or some local culture hero will appear and inaugurate a blissful paradise on earth. Death, old age, illness and evil will be unknown. The riches of the white man will accrue to the Melanesians." In 1960, the celebrated naturalist David Attenborough created a documentary The People of Paradise: Cargo Cult.18 Attenborough travels through the island of Tanna and encounters many artifacts of the John Frum cult, such as symbolic gates and crosses, painted brilliant scarlet and decorated with objects such as a shaving brush, a winged rat, and a small carved airplane. Attenborough interviews a cult leader who claims to have talked with the mythical John Frum, said to be a white American. The leader remains in communication with John Frum through a tall pole said to be a radio mast, and an unseen radio. (The "radio" consisted of an old woman with electrical wire wrapper around her waist, who would speak gibberish in a trance.) "Symbols of the cargo cult." In the center, a representation of John Frum with "scarlet coat and a white European face" stands behind a brilliantly painted cross. A wooden airplane is on the right, while on the left (outside the photo) a cage contains a winged rat. From Journeys to the Past, which describes Attenborough's visit to the island of Tanna. In 1963, famed anthropologist Margaret Mead brought cargo cults to the general public, writing Where Americans are Gods: The Strange Story of the Cargo Cults in the mass-market newspaper supplement Family Weekly. In just over a page, this article describes the history of cargo cults before, during, and after World War II.19 One cult sat around a table with vases of colorful flowers on them. Another cult threw away their money. Another cult watched for ships from hilltops, expecting John Frum to bring a fleet of ships bearing cargo from the land of the dead. One of the strangest cargo cults was a group of 2000 people on New Hanover Island, "collecting money to buy President Johnson of the United States [who] would arrive with other Americans on the liner Queen Mary and helicopters next Tuesday." The islanders raised $2000, expecting American cargo to follow the president. Seeing the name Johnson on outboard motors confirmed their belief that President Johnson was personally sending cargo.20 A 1971 article in Time Magazine22 described how tribesmen brought US Army concrete survey markers down from a mountaintop while reciting the Roman Catholic rosary, dropping the heavy markers outside the Australian government office. They expected that "a fleet of 500 jet transports would disgorge thousands of sympathetic Americans bearing crates of knives, steel axes, rifles, mirrors and other wonders." Time magazine explained the “cargo cult” as "a conviction that if only the dark-skinned people can hit on the magic formula, they can, without working, acquire all the wealth and possessions that seem concentrated in the white world... They believe that everything has a deity who has to be contacted through ritual and who only then will deliver the cargo." Cult leaders tried "to duplicate the white man’s magic. They hacked airstrips in the rain forest, but no planes came. They built structures that look like white men’s banks, but no money materialized."21 National Geographic, in an article Head-hunters in Today's World (1972), mentioned a cargo-cult landing field with a replica of a radio aerial, created by villagers who hoped that it would attract airplanes bearing gifts. It also described a cult leader in South Papua who claimed to obtain airplanes and cans of food from a hole in the ground. If the people believed in him, their skins would turn white and he would lead them to freedom. These sources and many others23 illustrate that cargo cults do not fit a simple story. Instead, cargo cults are extremely varied, happening across thousands of miles and many decades. The lack of common features between cargo cults leads some anthropologists to reject the idea of cargo cults as a meaningful term.24 In any case, most historical cargo cults have very little in common with the pop-culture description of a cargo cult. Isles of the South Pacific, 1968.](nampas.jpg "w300") --> Cargo beliefs were inspired by Christianity Cargo cult beliefs are closely tied to Christianity, a factor that is ignored in pop-culture descriptions of cargo cults. Beginning in the mid-1800s, Christian missionaries set up churches in New Guinea to convert the inhabitants. As a result, cargo cults incorporated Christian ideas, but in very confusing ways. At first, the natives believed that missionaries had come to reveal the ritual secrets and restore the cargo. By enthusiastically joining the church, singing the hymns, and following the church's rituals, the people would be blessed by God, who would give them the cargo. This belief was common in the 1920s and 1930s, but as the years went on and the people didn't receive the cargo, they theorized that the missionaries had removed the first pages of the Bible to hide the cargo secrets. A typical belief was that God created Adam and Eve in Paradise, "giving them cargo: tinned meat, steel tools, rice in bags, tobacco in tins, and matches, but not cotton clothing." When Adam and Eve offended God by having sexual intercourse, God threw them out of Paradise and took their cargo. Eventually, God sent the Flood but Noah was saved in a steamship and God gave back the cargo. Noah's son Ham offended God, so God took the cargo away from Ham and sent him to New Guinea, where he became the ancestor of the natives. Other natives believed that God lived in Heaven, which was in the clouds and reachable by ladder from Sydney, Australia (source). God, along with the ancestors, created cargo in Heaven—"tinned meat, bags of rice, steel tools, cotton cloth, tinned tobacco, and a machine for making electric light"—which would be flown from Sydney and delivered to the natives, who thus needed to clear an airstrip (source).25 Another common belief was that symbolic radios could be used to communicate with Jesus. For instance, a Markham Valley cargo group in 1943 created large radio houses so they could be informed of the imminent Coming of Jesus, at which point the natives would expel the whites (source). The "radio" consisted of bamboo cylinders connected to a rope "aerial" strung between two poles. The houses contained a pole with rungs so the natives could climb to Jesus along with cane "flashlights" to see Jesus. A tall mast with a flag and cross on top. This was claimed to be a special radio mast that enabled communication with John Frum. It was decorated with scarlet leaves and flowers. From Attenborough's Cargo Cult. Mock radio antennas are also discussed in a 1943 report26 from a wartime patrol that found a bamboo "wireless house", 42 feet in diameter. It had two long poles outside and with an "aerial" of rope between them, connected to the "radio" inside, a bamboo cylinder. Villagers explained that the "radio" was to receive messages of the return of Jesus, who would provide weapons for the overthrow of white rule. The villagers constructed ladders outside the house so they could climb up to the Christian God after death. They would shed their skin like a snake, getting a new white skin, and then they would receive the "boats and white men's clothing, goods, etc." Mondo Cane and the creation of the pop-culture cargo cult As described above, cargo cults expected the cargo to arrive by ships much more often than airplanes. So why do pop-culture cargo cults have detailed descriptions of runways, airplanes, wooden headphones, and bamboo control towers?27 My hypothesis is that it came from a 1962 movie called Mondo Cane. This film was the first "shockumentary", showing extreme and shocking scenes from around the world. Although the film was highly controversial, it was shown at the Cannes Film Festival and was a box-office success. The film made extensive use of New Guinea with multiple scandalous segments, such as a group of "love-struck" topless women chasing men,29 a woman breastfeeding a pig, and women in cages being fattened for marriage. The last segment in the movie showed "the cult of the cargo plane": natives forlornly watching planes at the airport, followed by scenes of a bamboo airplane sitting on a mountaintop "runway" along with bamboo control towers. The natives waited all day and then lit torches to illuminate the runway at nightfall. These scenes are very similar to the pop-culture descriptions of cargo cults so I suspect this movie is the source. A still from the 1962 movie "Mondo Cane", showing a bamboo airplane sitting on a runway, with flaming torches acting as beacons. I have my doubts about its accuracy. The film claims that all the scenes "are true and taken only from life", but many of the scenes are said to be staged. Since the cargo cult scenes are very different from anthropological reports and much more dramatic, I think they were also staged and exaggerated.28 It is known that the makers of Mondo Cane paid the Melanesian natives generously for the filming (source, source). Did Feynman get his cargo cult ideas from Mondo Cane? It may seem implausible since the movie was released over a decade earlier. However, the movie became a cult classic, was periodically shown in theaters, and influenced academics.30 In particular, Mondo Cane showed at the famed Cameo theater in downtown Los Angeles on April 3, 1974, two months before Feynman's commencement speech. Mondo Cane seems like the type of offbeat movie that Feynman would see and the theater was just 11 miles from Caltech. While I can't prove that Feynman went to the showing, his description of a cargo cult strongly resembles the movie.31 Fake cargo-cult photos fill the internet Fakes and hoaxes make researching cargo cults online difficult. There are numerous photos online of cargo cults, but many of these photos are completely made up. For instance, the photo below has illustrated cargo cults for articles such as Cargo Cult, UX personas are useless, A word on cargo cults, The UK Integrated Review and security sector innovation, and Don't be a cargo cult. However, this photo is from a Japanese straw festival and has nothing to do with cargo cults. An airplane built from straw, one creation at a Japanese straw festival. I've labeled the photo with "Not cargo cult" to ensure it doesn't get reused in cargo cult articles. Another example is the photo below, supposedly an antenna created by a cargo cult. However, it is actually a replica of the Jodrell Bank radio telescope, built in 2007 by a British farmer from six tons of straw (details). The farmer's replica ended up erroneously illustrating Cargo Cult Politics, The Cargo Cult & Beliefs, The Cargo Cult, Cargo Cults of the South Pacific, and Cargo Cult, among others.32 A British farmer created this replica radio telescope. Photo by Mike Peel, (CC BY-SA 4.0). Other articles illustrate cargo cults with the aircraft below, suspiciously sleek and well-constructed. However, the photo actually shows a wooden wind tunnel model of the Buran spacecraft, abandoned at a Russian airfield as described in this article. Some uses of the photo are Are you guilty of “cargo cult” thinking without even knowing it? and The Cargo Cult of Wealth. This is an abandoned Soviet wind tunnel model of the Buran spacecraft. Photo by Aleksandr Markin. Many cargo cult articles use one of the photo below. I tracked them down to the 1970 movie "Chariots of the Gods" (link), a dubious documentary claiming that aliens have visited Earth throughout history. The segment on cargo cults is similar to Mondo Cane with cultists surrounding a mock plane on a mountaintop, lighting fires along the runway. However, it is clearly faked, probably in Africa: the people don't look like Pacific Islanders and are wearing wigs. One participant wears leopard skin (leopards don't live in the South Pacific). The vegetation is another giveaway: the plants are from Africa, not the South Pacific.33 Two photos of a straw plane from "Chariots of the Gods". The point is that most of the images that illustrate cargo cults online are fake or wrong. Most internet photos and information about cargo cults have just been copied from page to page. (And now we have AI-generated cargo cult photos.) If a photo doesn't have a clear source (including who, when, and where), don't believe it. Conclusions The cargo cult metaphor should be avoided for three reasons. First, the metaphor is essentially meaningless and heavily overused. The influential "Jargon File" defined cargo-cult programming as "A style of (incompetent) programming dominated by ritual inclusion of code or program structures that serve no real purpose."34 Note that the metaphor in cargo-cult programming is the opposite of the metaphor in cargo-cult science: Feyman's cargo-cult science has no chance of working, while cargo-cult programming works but isn't understood. Moreover, both metaphors differ from the cargo-cult metaphor in other contexts, referring to the expectation of receiving valuables without working.35 The popular site Hacker News is an example of how "cargo cult" can be applied to anything: agile programming, artificial intelligence, cleaning your desk. Go, hatred of Perl, key rotation, layoffs, MBA programs, microservices, new drugs, quantum computing, static linking, test-driven development, and updating the copyright year are just a few things that are called "cargo cult".36 At this point, cargo cult is simply a lazy, meaningless attack. The second problem with "cargo cult" is that the pop-culture description of cargo cults is historically inaccurate. Actual cargo cults are much more complex and include a much wider (and stranger) variety of behaviors. Cargo cults started before World War II and involve ships more often than airplanes. Cargo cults mix aspects of paganism and Christianity, often with apocalyptic ideas of the end of the current era, the overthrow of white rule, and the return of dead ancestors. The pop-culture description discards all this complexity, replacing it with a myth. Finally, the cargo cult metaphor turns decades of harmful colonialism into a humorous anecdote. Feynman's description of cargo cults strips out the moral complexity: US soldiers show up with their cargo and planes, the indigenous residents amusingly misunderstand the situation, and everyone carries on. However, cargo cults really were a response to decades of colonial mistreatment, exploitation, and cultural destruction. Moreover, cargo cults were often harmful: expecting a bounty of cargo, villagers would throw away their money, kill their pigs, and stop tending their crops, resulting in famine. The pop-culture cargo cult erases the decades of colonial oppression, along with the cultural upheaval and deaths from World War II. Melanesians deserve to be more than the punch line in a cargo cult story. Thus, it's time to move beyond the cargo cult metaphor. Notes and references As an illustration of the popularity of Feynman's "Cargo Cult Science" commencement address, it has been on Hacker News at least 15 times. ↩ The first cargo cult definition above comes from The Trumpet Shall Sound; A Study of "Cargo" Cults in Melanesia. The second definition is from the Cargo Cult entry in The Open Encyclopedia of Anthropology. Written by Lamont Lindstrom, a professor who studies Melanesia, the entry comprehensively describes the history and variety of cargo cults, as well as current anthropological analysis. For an early anthropological theory of cargo cults, see An Empirical Case-Study: The Problem of Cargo Cults in "The Revolution in Anthropology" (Jarvie, 1964). This book categorizes cargo cults as an apocalyptic millenarian religious movement with a central tenet: When the millennium comes it will largely consist of the arrival of ships and/or aeroplanes loaded up with cargo; a cargo consisting either of material goods the natives long for (and which are delivered to the whites in this manner), or of the ancestors, or of both.  ↩ European colonization brought pacification and a reduction in violence. The Cargo Cult: A Melanesian Type-Response to Change describes this pacification and termination of warfare as the Pax Imperii, suggesting that pacification came as a relief to the Melanesians: "They welcomed the cessation of many of the concomitants of warfare: the sneak attack, ambush, raiding, kidnapping of women and children, cannibalism, torture, extreme indignities inflicted on captives, and the continual need to be concerned with defense." That article calls the peace the Pax Imperii. Warfare among the Enga people of New Guinea is described in From Spears to M-16s: Testing the Imbalance of Power Hypothesis among the Enga. The Enga engaged in tribal warfare for reasons such as "theft of game from traps, quarrels over possessions, or work sharing within the group." The surviving losers were usually driven off the land and forced to settle elsewhere. In the 1930s and 1940s, the Australian administration banned tribal fighting and pacified much of the area. However, after the independence of Papua New Guinea in 1975, warfare increased along with the creation of criminal gangs known as Raskols (rascals). The situation worsened in the late 1980s with the introduction of shotguns and high-powered weapons to warfare. Now, Papua New Guinea has one of the highest crime rates in the world along with one of the lowest police-to-population ratios in the world. ↩ When you hear tales of cannibalism, some skepticism is warranted. However, cannibalism is proved by the prevalence of kuru, or "laughing sickness", a fatal prion disease (transmissible spongiform encephalopathy) spread by consuming human brains. Also see Headhunters in Today's World, a 1972 National Geographic article that describes the baking of heads and the eating of brains. ↩ A 1957 dictionary of Pidgin English can be found here. Linguistically, Tok Pisin is a creole, not a pidgin. ↩ The modern view is that countries such as Great Britain acquired colonies against the will of the colonized, but the situation was more complex in the 19th century. Many Pacific islands desperately wanted to become European colonies, but were turned down for years because the countries were viewed as undesiable burdens. For example, Fiji viewed colonization as the solution to the chaos caused by the influx of white settlers in the 1800s. Fijian political leaders attempted to cede the islands to a European power that could end the lawlessness, but were turned down. In 1874, the situation changed when Disraeli was elected British prime minister. His pro-imperial policies, along with the Royal Navy's interest in obtaining a coaling station, concerns about American expansion, and pressure from anti-slavery groups, led to the annexation of Fiji by Britain. The situation in Fiji didn't particularly improve from annexation. (Fiji obtained independence almost a century later, in 1970.) As an example of the cost of a colony, Australia was subsidizing Papua New Guinea (with a population of 2.5 million) with over 100 million dollars a year in the early 1970s. (source) ↩ When reading about colonial Melanesia, one notices a constant background of police activity. Even when police patrols were very rare (annual in some parts), they were typically accompanied by arbitrary arrests and imprisonment. The most common cause for arrest was adultery; it may seem strange that the police were so concerned with it, but it turns out that adultery was the most common cause of warfare between tribes, and the authorities were trying to reduce the level of warfare. Cargo cult activity could be punished by six months of imprisonment. Jailing tended to be ineffective in stopping cargo cults, however, as it was viewed as evidence that the Europeans were trying to stop the cult leaders from spreading the cargo secrets that they had uncovered. ↩ See The Trumpet Shall Sound. ↩ The government imposed a head tax, which for the most part could only be paid through employment. A 1924 report states, "The primary object of the head tax was not to collect revenue but to create among the natives a need for money, which would make labour for Europeans desirable and would force the natives to accept employment." ↩ The Papua Annual Report, 1919-20 includes a report on the "Vailala Madness", starting on page 118. It describes how villages with the "Vialala madness" had "ornamented flag-poles, long tables, and forms or benches, the tables being usually decorated with flowers in bottles of water in imitation of a white man's dining table." Village men would sit motionless with their backs to the tables. Their idleness infuriated the white men, who considered the villagers to be "fit subjects for a lunatic asylum." ↩ The Vailala Madness is also described in The Missionary Review of the World, 1924. The Vaialala Madness also involved seizure-like physical aspects, which typically didn't appear in later cargo cult behavior. The 1957 book The Trumpet Shall Sound: A Study of "Cargo" Cults in Melanesia is an extensive discussion of cargo cults, as well as earlier activity and movements. Chapter 4 covers the Vailala Madness in detail. ↩ The battles in the Pacific have been extensively described from the American and Japanese perspectives, but the indigenous residents of these islands are usually left out of the narratives. This review discusses two books that provide the Melanesian perspective. I came across the incredible story of Sergeant Major Vouza of the Native Constabulary. While this story is not directly related to cargo cults, I wanted to include it as it illustrates the dedication and suffering of the New Guinea natives during World War II. Vouza volunteered to scout behind enemy lines for the Marines at Guadalcanal but he was captured by the Japanese, tied to a tree, tortured, bayonetted, and left for dead. He chewed through his ropes, made his way through the enemy force, and warned the Marines of an impending enemy attack. SgtMaj Vouza, British Solomon Islands Constabulary. From The Guadalcanal Campaign, 1949. Vouza described the event in a letter: Letter from SgtMaj Vouza to Hector MacQuarrie, 1984. From The Guadalcanal Campaign.  ↩ The Japanese occupation and the cargo cult started by Tagareb are described in detail in Road Belong Cargo, pages 98-110. ↩ See "John Frum Movement in Tanna", Oceania, March 1952. The New York Times described the John Frum movement in detail in a 1970 article: "On a Pacific island, they wait for the G.I. who became a God". A more modern article (2006) on John Frum is In John They Trust in the Smithsonian Magazine. As for the identity of John Frum, some claim that his name is short for "John from America". Others claim it is a modification of "John Broom" who would sweep away the whites. These claims lack evidence. ↩ The quote is from Pacific Islands Monthly, November 1945 (link). The National Library of Australia has an extensive collection of issues of Pacific Islands Monthly online. Searching these magazines for "cargo cult" provides an interesting look at how cargo cults were viewed as they happened. ↩ Scientific American had a long article titled Cargo Cults in May 1959, written by Peter Worsley, who also wrote the classic book The Trumpet Shall Sound: A Study of 'Cargo' Cults in Melanesia. The article lists the following features of cargo cults: Myth of the return of the dead Revival or modification of paganism Introduction of Christian elements Cargo myth Belief that Negroes will become white men and vice versa Belief in a coming messiah Attempts to restore native political and economic control Threats and violence against white men Union of traditionally separate and unfriendly groups Different cargo cults contained different subsets of these features but no specific feature The article is reprinted here; the detailed maps show the wide distribution of cargo cults. ↩↩ See A Cargo Movement in the Eastern Central Highlands of New Guinea, Oceania, 1952. ↩↩ The Attenborough Cargo Cult documentary can be watched on YouTube. I'll summarize some highlights with timestamps: 5:20: A gate, palisade, and a cross all painted brilliant red. 6:38: A cross decorated with a wooden bird and a shaving brush. 7:00: A tall pole claimed to be a special radio mast to talk with John Frum. 8:25: Interview with trader Bob Paul. He describes "troops" marching with wooden guns around the whole island. 12:00: Preparation and consumption of kava, the intoxicating beverage. 13:08: Interview with a local about John Frum. 14:16: John Frum described as a white man and a big fellow. 16:29: Attenborough asks, "You say John Frum has not come for 19 years. Isn't this a long time for you to wait?" The leader responds, "No, I can wait. It's you waiting for two thousand years for Christ to come and I must wait over 19 years." Attenborough accepts this as a fair point. 17:23: Another scarlet gate, on the way to the volcano, with a cross, figure, and model airplane. 22:30: Interview with the leader. There's a discussion of the radio, but Attenborough is not allowed to see it. 24:21: John Frum is described as a white American. The expedition is also described in David Attenborough's 1962 book Quest in Paradise.  ↩ I have to criticize Mead's article for centering Americans as the heroes, almost a parody of American triumphalism. The title sets the article's tone: "Where Americans are Gods..." The article explains, "The Americans were lavish. They gave away Uncle Sam's property with a generosity which appealed mightily... so many kind, generous people, all alike, with such magnificent cargoes! The American servicemen, in turn, enjoyed and indulged the islanders." The article views cargo cults as a temporary stage before moving to a prosperous American-style society as islanders realized that "American things could come [...] only by work, education, persistence." A movement leader named Paliau is approvingly quoted: "We would like to have the things Americans have. [...] We think Americans have all these things because they live under law, without endless quarrels. So we must first set up a new society." On the other hand, by most reports, the Americans treated the residents of Melanesia much better than the colonial administrators. Americans paid the natives much more (which was viewed as overpaying them by the planters). The Americans treated the natives with much more respect; natives worked with Americans almost as equals. Finally, it appeared to the natives that black soldiers were treated as equals to white soldiers. (Obviously, this wasn't entirely accurate.) The Melanesian experience with Americans also strengthened Melanesian demands for independence. Following the war, the reversion to colonial administration produced a lot of discontent in the natives, who realized that their situation could be much better. (See World War II and Melanesian self-determination.) ↩ The Johnson cult was analyzed in depth by Billings, an anthropologist who wrote about it in Cargo Cult as Theater: Political Performance in the Pacific. See also Australian Daily News, June 12, 1964, and Time Magazine, July 19, 1971. ↩ In one unusual case, the islanders built an airstrip and airplanes did come. Specifically, the Miyanmin people of New Guinea hacked an airstrip out of the forest in 1966 using hand tools. The airstrip was discovered by a patrol and turned out to be usable, so Baptist missionaries made monthly landings, bringing medicine and goods for a store. It is pointed out that the only thing preventing this activity from being considered a cargo cult is that in this case, it was effective. See A Small Footnote to the 'Big Walk', p. 59. ↩ See "New Guinea: Waiting for That Cargo", Time Magazine, July 19, 1971.  ↩ In this footnote, I'll list some interesting cargo cult stories that didn't fit into the body of the article. The 1964 US Bureau of Labor Statistics report on New Guinea describes cargo cults: "A simplified explanation of them is often given namely that contact with Western culture has given the indigene a desire for a better economic standard of living this desire has not been accompanied by the understanding that economic prosperity is achieved by human effort. The term cargo cult derives from the mystical expectation of the imminent arrival by sea or air of the good things of this earth. It is believed sufficient to build warehouses of leaves and prepare air strips to receive these goods. Activity in the food gardens and daily community routine chores is often neglected so that economic distress is engendered." Cargo Cult Activity in Tangu (Burridge) is a 1954 anthropological paper discussing stories of three cargo cults in Tangu, a region of New Guinea. The first involved dancing around a man in a trance, which was supposed to result in the appearance of "rice, canned meat, lava-lavas, knives, beads, etc." In the second story, villagers built a shed in a cemetery and then engaged in ritualized sex acts, expecting the shed to be filled with goods. However, the authorities forced the participants to dismantle the shed and throw it into the sea. In the third story, the protagonist is Mambu, who stowed away on a steamship to Australia, where he discovered the secrets of the white man's cargo. On his return, he collected money to help force the Europeans out, until he was jailed. He performed "miracles" by appearing outside jail as well as by producing money out of thin air. Reaction to Contact in the Eastern Highlands of New Guinea (Berndt, 1954) has a long story about Berebi, a leader who was promised a rifle, axes, cloth, knives, and valuable cowrie by a white spirit. Berebi convinces his villagers to build storehouses and they filled the houses with stones that would be replaced by goods. They take part in many pig sacrifices and various rituals, and endure attacks of shivering and paralysis, but they fail to receive any goods and Berebi concludes that the spirit deceived him. ↩ Many anthropologists view the idea of cargo cults as controversial. One anthropologist states, "What I want to suggest here is that, similarly, cargo cults do not exist, or at least their symptoms vanish when we start to doubt that we can arbitrarily extract a few features from context and label them an institution." See A Note on Cargo Cults and Cultural Constructions of Change (1988). The 1992 paper The Yali Movement in Retrospect: Rewriting History, Redefining 'Cargo Cult' summarizes the uneasiness that many anthropologists have with the term "cargo cult", viewing it as "tantamount to an invocation of colonial power relationships." The book Cargo, Cult, and Culture Critique (2004) states, "Some authors plead quite convincingly for the abolition of the term itself, not only because of its troublesome implications, but also because, in their view, cargo cults do not even exist as an identifiable object of study." One paper states that the phrase is both inaccurate and necessary, proposing that it be written crossed-out (sous rature in Derrida's post-modern language). Another paper states: "Cargo cults defy definition. They are inherently troublesome and problematic," but concludes that the term is useful precisely because of this troublesome nature. At first, I considered the idea of abandoning the label "cargo cult" to be absurd, but after reading the anthropological arguments, it makes more sense. In particular, the category "cargo cult" is excessively broad, lumping together unrelated things and forcing them into a Procrustean ideal: John Frum has very little in common with Vaialala Madness, let alone the Johnson Cult. I think that the term "cargo cult" became popular due to its catchy, alliterative name. (Journalists love alliterations such as "Digital Divide" or "Quiet Quitting".) ↩ It was clear to the natives that the ancestors, and not the Europeans, must have created the cargo because the local Europeans were unable to repair complex mechanical devices locally, but had to ship them off. These ships presumably took the broken devices back to the ancestral spirits to be repaired. Source: The Trumpet Shall Sound, p119. ↩ The report from the 1943 patrol is discussed in Berndt's "A Cargo Movement in the Eastern Central Highlands of New Guinea", Oceania, Mar. 1953 (link), page 227. These radio houses are also discussed in The Trumpet Shall Sound, page 199. ↩ Wooden airplanes are a staple of the pop-culture cargo cult story, but they are extremely rare in authentic cargo cults. I searched extensively, but could find just a few primary sources that involve airplanes. The closest match that I could find is Vanishing Peoples of the Earth, published by National Geographic in 1968, which mentions a New Guinea village that built a "crude wooden airplane", which they thought "offers the key to getting cargo". The photo below, from 1950, shows a cargo-house built in the shape of an airplane. (Note how abstract the construction is, compared to the realistic straw airplanes in faked photos.) The photographer mentioned that another cargo house was in the shape of a jeep, while in another village, the villagers gather in a circle at midnight to await the arrival of heavily laden cargo boats. The photo is from They Still Believe in Cargo Cult, Pacific Islands Monthly, May 1950. David Attenborough's Cargo Cult documentary shows a small wooden airplane, painted scarlet red. This model airplane is very small compared to the mock airplanes described in the pop-culture cargo cult. A closeup of the model airplane. From Attenborough's Cargo Cult documentary. The photo below shows the scale of the aircraft, directly in front of Attenborough. In the center, a figure of John Frum has a "scarlet coat and a white, European face." On the left, a cage contains a winged rat for some reason. David Attenborough visiting a John Frum monument on Tanna, near Sulfur Bay. From Attenborough's Cargo Cult documentary.  ↩ The photo below shows another scene from the movie Mondo Cane that is very popular online in cargo cult articles. I suspect that the airplane is not authentic but was made for the movie. Screenshot from Mondo Cane, showing the cargo cultists posed in front of their airplane.  ↩ The tale of women pursuing men was described in detail in the 1929 anthropological book The Sexual Life of Savages in North-Western Melanesia, specifically the section "Yausa—Orgiastic Assaults by Women" (pages 231-234). The anthropologist heard stories about these attacks from natives, but didn't observe them firsthand and remained skeptical. He concluded that "The most that can be said with certainty is that the yausa, if it happened at all, happened extremely rarely". Unlike the portrayal in Mondo Cane, these attacks on men were violent and extremely unpleasant (I won't go into details). Thus, it is very likely that this scene in Mondo Cane was staged, based on the stories. ↩ The movie Mondo Cane directly influenced the pop-culture cargo cult as shown by several books. The book River of Tears: The Rise of the Rio Tinto-Zinc Mining Corporation explains cargo cults and how one tribe built an "aeroplane on a hilltop to attract the white man's aeroplane and its cargo", citing Mondo Cane. Likewise, the book Introducing Social Change states that underdeveloped nations are moving directly from ships to airplanes without building railroads, bizarrely using the cargo cult scene in Mondo Cane as an example. Finally, the religious book Open Letter to God uses the cargo cult in Mondo Cane as an example of the suffering of godless people. ↩ Another possibility is that Feynman got his cargo cult ideas from the 1974 book Cows, Pigs, Wars and Witches: The Riddle of Culture. It has a chapter "Phantom Cargo", which starts with a description suspiciously similar to the scene in Mondo Cane: The scene is a jungle airstrip high in the mountains of New Guinea. Nearby are thatch-roofed hangars, a radio shack, and a beacon tower made of bamboo. On the ground is an airplane made of sticks and leaves. The airstrip is manned twenty-four hours a day by a group of natives wearing nose ornaments and shell armbands. At night they keep a bonfire going to serve as a beacon. They are expecting the arrival of an important flight: cargo planes filled with canned food, clothing, portable radios, wrist watches, and motorcycles. The planes will be piloted by ancestors who have come back to life. Why the delay? A man goes inside the radio shack and gives instructions into the tin-can microphone. The message goes out over an antenna constructed of string and vines: “Do you read me? Roger and out.” From time to time they watch a jet trail crossing the sky; occasionally they hear the sound of distant motors. The ancestors are overhead! They are looking for them. But the whites in the towns below are also sending messages. The ancestors are confused. They land at the wrong airport.  ↩ Some other uses of the radio telescope photo as a cargo-cult item are Cargo cults, Melanesian cargo cults and the unquenchable thirst of consumerism, Cargo Cult : Correlation vs. Causation, Cargo Cult Agile, Stop looking for silver bullets, and Cargo Cult Investing. ↩ Chariots of the Gods claims to be showing a cargo cult from an isolated island in the South Pacific. However, the large succulent plants in the scene are Euphorbia ingens and tree aloe, which grow in southern Africa, not the South Pacific. The rock formations at the very beginning look a lot like Matobo Hills in Zimbabwe. Note that these "Stone Age" people are astounded by the modern world but ignore the cameraman who is walking among them. Many cargo cults articles use photos that can be traced back from this film, such as The Scrum Cargo Cult, Is Your UX Cargo Cult, The Remote South Pacific Island Where They Worship Planes, The Design of Everyday Games, Don’t be Fooled by the Bitcoin Core Cargo Cult, The Dying Art of Design, Retail Apocalypse Not, You Are Not Google, and Cargo Cults. The general theme of these articles is that you shouldn't copy what other people are doing without understanding it, which is somewhat ironic. ↩ The Jargon File defined "cargo-cult programming" in 1991: cargo-cult programming: n. A style of (incompetent) programming dominated by ritual inclusion of code or program structures that serve no real purpose. A cargo-cult programmer will usually explain the extra code as a way of working around some bug encountered in the past, but usually, neither the bug nor the reason the code avoided the bug were ever fully understood. The term cargo-cult is a reference to aboriginal religions that grew up in the South Pacific after World War II. The practices of these cults center on building elaborate mockups of airplanes and military style landing strips in the hope of bringing the return of the god-like airplanes that brought such marvelous cargo during the war. Hackish usage probably derives from Richard Feynman's characterization of certain practices as "cargo-cult science" in `Surely You're Joking, Mr. Feynman'. This definition of "cargo-cult programming" came from a 1991 Usenet post to alt.folklore.computers, quoting Kent Williams. The definition was added to the much-expanded 1991 Jargon File, which was published as The New Hacker's Dictionary in 1993. ↩ Overuse of the cargo cult metaphor isn't specific to programming, of course. The book Cargo Cult: Strange Stories of Desire from Melanesia and Beyond describes how "cargo cult" has been applied to everything from advertisements, social welfare policy, and shoplifting to the Mormons, Euro Disney, and the state of New Mexico. This book, by Lamont Linstrom, provides a thorough analysis of writings on cargo cults. It takes a questioning, somewhat trenchant look at these writings, illuminating the development of trends in these writings and the lack of objectivity. I recommend this book to anyone interested in the term "cargo cult" and its history. ↩ Some more things that have been called "cargo cult" on Hacker News: the American worldview, ChatGPT fiction, copy and pasting code, hiring, HR, priorities, psychiatry, quantitative tests, religion, SSRI medication, the tech industry, Uber, and young-earth creationism. ↩

Intel released the powerful Pentium processor in 1993, establishing a long-running brand of high-performance processors.1 The Pentium includes a floating-point unit that can rapidly compute functions such as sines, cosines, logarithms, and exponentials. But how does the Pentium compute these functions? Earlier Intel chips used binary algorithms called CORDIC, but the Pentium switched to polynomials to approximate these transcendental functions much faster. The polynomials have carefully-optimized coefficients that are stored in a special ROM inside the chip's floating-point unit. Even though the Pentium is a complex chip with 3.1 million transistors, it is possible to see these transistors under a microscope and read out these constants. The first part of this post discusses how the floating point constant ROM is implemented in hardware. The second part explains how the Pentium uses these constants to evaluate sin, log, and other functions. The photo below shows the Pentium's thumbnail-sized silicon die under a microscope. I've labeled the main functional blocks; the floating-point unit is in the lower right. The constant ROM (highlighted) is at the bottom of the floating-point unit. Above the floating-point unit, the microcode ROM holds micro-instructions, the individual steps for complex instructions. To execute an instruction such as sine, the microcode ROM directs the floating-point unit through dozens of steps to compute the approximation polynomial using constants from the constant ROM. Die photo of the Intel Pentium processor with the floating point constant ROM highlighted in red. Click this image (or any other) for a larger version. Finding pi in the constant ROM In binary, pi is 11.00100100001111110... but what does this mean? To interpret this, the value 11 to the left of the binary point is simply 3 in binary. (The "binary point" is the same as a decimal point, except for binary.) The digits to the right of the binary point have the values 1/2, 1/4, 1/8, and so forth. Thus, the binary value `11.001001000011... corresponds to 3 + 1/8 + 1/64 + 1/4096 + 1/8192 + ..., which matches the decimal value of pi. Since pi is irrational, the bit sequence is infinite and non-repeating; the value in the ROM is truncated to 67 bits and stored as a floating point number. A floating point number is represented by two parts: the exponent and the significand. Floating point numbers include very large numbers such as 6.02×1023 and very small numbers such as 1.055×10−34. In decimal, 6.02×1023 has a significand (or mantissa) of 6.02, multiplied by a power of 10 with an exponent of 23. In binary, a floating point number is represented similarly, with a significand and exponent, except the significand is multiplied by a power of 2 rather than 10. For example, pi is represented in floating point as 1.1001001...×21. The diagram below shows how pi is encoded in the Pentium chip. Zooming in shows the constant ROM. Zooming in on a small part of the ROM shows the rows of transistors that store the constants. The arrows point to the transistors representing the bit sequence 11001001, where a 0 bit is represented by a transistor (vertical white line) and a 1 bit is represented by no transistor (solid dark silicon). Each magnified black rectangle at the bottom has two potential transistors, storing two bits. The key point is that by looking at the pattern of stripes, we can determine the pattern of transistors and thus the value of each constant, pi in this case. A portion of the floating-point ROM, showing the value of pi. Click this image (or any other) for a larger version. The bits are spread out because each row of the ROM holds eight interleaved constants to improve the layout. Above the ROM bits, multiplexer circuitry selects the desired constant from the eight in the activated row. In other words, by selecting a row and then one of the eight constants in the row, one of the 304 constants in the ROM is accessed. The ROM stores many more digits of pi than shown here; the diagram shows 8 of the 67 significand bits. Implementation of the constant ROM The ROM is built from MOS (metal-oxide-semiconductor) transistors, the transistors used in all modern computers. The diagram below shows the structure of an MOS transistor. An integrated circuit is constructed from a silicon substrate. Regions of the silicon are doped with impurities to create "diffusion" regions with desired electrical properties. The transistor can be viewed as a switch, allowing current to flow between two diffusion regions called the source and drain. The transistor is controlled by the gate, made of a special type of silicon called polysilicon. Applying voltage to the gate lets current flow between the source and drain, which is otherwise blocked. Most computers use two types of MOS transistors: NMOS and PMOS. The two types have similar construction but reverse the doping; NMOS uses n-type diffusion regions as shown below, while PMOS uses p-type diffusion regions. Since the two types are complementary (C), circuits built with the two types of transistors are called CMOS. Structure of a MOSFET in an integrated circuit. The image below shows how a transistor in the ROM looks under the microscope. The pinkish regions are the doped silicon that forms the transistor's source and drain. The vertical white line is the polysilicon that forms the transistor's gate. For this photo, I removed the chip's three layers of metal, leaving just the underlying silicon and the polysilicon. The circles in the source and drain are tungsten contacts that connect the silicon to the metal layer above. One transistor in the constant ROM. The diagram below shows eight bits of storage. Each of the four pink silicon rectangles has two potential transistors. If a polysilicon gate crosses the silicon, a transistor is formed; otherwise there is no transistor. When a select line (horizontal polysilicon) is energized, it will turn on all the transistors in that row. If a transistor is present, the corresponding ROM bit is 0 because the transistor will pull the output line to ground. If a transistor is absent, the ROM bit is 1. Thus, the pattern of transistors determines the data stored in the ROM. The ROM holds 26144 bits (304 words of 86 bits) so it has 26144 potential transistors. Eight bits of storage in the ROM. The photo below shows the bottom layer of metal (M1): vertical metal wires that provide the ROM outputs and supply ground to the ROM. (These wires are represented by gray lines in the schematic above.) The polysilicon transistors (or gaps as appropriate) are barely visible between the metal lines. Most of the small circles are tungsten contacts to the silicon or polysilicon; compare with the photo above. Other circles are tungsten vias to the metal layer on top (M2), horizontal wiring that I removed for this photo. The smaller metal "tabs" act as jumpers between the horizontal metal select lines in M2 and the polysilicon select lines. The top metal layer (M3, not visible) has thicker vertical wiring for the chip's primary distribution power and ground. Thus, the three metal layers alternate between horizontal and vertical wiring, with vias between the layers. A closeup of the ROM showing the bottom metal layer. The ROM is implemented as two grids of cells (below): one to hold exponents and one to hold significands, as shown below. The exponent grid (on the left) has 38 rows and 144 columns of transistors, while the significand grid (on the right) has 38 rows and 544 columns. To make the layout work better, each row holds eight different constants; the bits are interleaved so the ROM holds the first bit of eight constants, then the second bit of eight constants, and so forth. Thus, with 38 rows, the ROM holds 304 constants; each constant has 18 bits in the exponent part and 68 bits in the significand section. A diagram of the constant ROM and supporting circuitry. Most of the significand ROM has been cut out to make it fit. The exponent part of each constant consists of 18 bits: a 17-bit exponent and one bit for the sign of the significand and thus the constant. There is no sign bit for the exponent because the exponent is stored with 65535 (0x0ffff) added to it, avoiding negative values. The 68-bit significand entry in the ROM consists of a mysterious flag bit2 followed by the 67-bit significand; the first bit of the significand is the integer part and the remainder is the fractional part.3 The complete contents of the ROM are in the appendix at the bottom of this post. To select a particular constant, the "row select" circuitry between the two sections activates one of the 38 rows. That row provides 144+544 bits to the selection circuitry above the ROM. This circuitry has 86 multiplexers; each multiplexer selects one bit out of the group of 8, selecting the desired constant. The significand bits flow into the floating-point unit datapath circuitry above the ROM. The exponent circuitry, however, is in the upper-left corner of the floating-point unit, a considerable distance from the ROM, so the exponent bits travel through a bus to the exponent circuitry. The row select circuitry consists of gates to decode the row number, along with high-current drivers to energize the selected row in the ROM. The photo below shows a closeup of two row driver circuits, next to some ROM cells. At the left, PMOS and NMOS transistors implement a gate to select the row. Next, larger NMOS and PMOS transistors form part of the driver. The large square structures are bipolar NPN transistors; the Pentium is unusual because it uses both bipolar transistors and CMOS, a technique called BiCMOS.4 Each driver occupies as much height as four rows of the ROM, so there are four drivers arranged horizontally; only one is visible in the photo. ROM drivers implemented with BiCMOS. Structure of the floating-point unit The floating-point unit is structured with data flowing vertically through horizontal functional units, as shown below. The functional units—adders, shifters, registers, and comparators—are arranged in rows. This collection of functional units with data flowing through them is called the datapath.5 The datapath of the floating-point unit. The ROM is at the bottom. Each functional unit is constructed from cells, one per bit, with the high-order bit on the left and the low-order bit on the right. Each cell has the same width—38.5 µm—so the functional units can be connected like Lego blocks snapping together, minimizing the wiring. The height of a functional unit varies as needed, depending on the complexity of the circuit. Functional units typically have 69 bits, but some are wider, so the edges of the datapath circuitry are ragged. This cell-based construction explains why the ROM has eight constants per row. A ROM bit requires a single transistor, which is much narrower than, say, an adder. Thus, putting one bit in each 38.5 µm cell would waste most of the space. Compacting the ROM bits into a narrow block would also be inefficient, requiring diagonal wiring to connect each ROM bit to the corresponding datapath bit. By putting eight bits for eight different constants into each cell, the width of a ROM cell matches the rest of the datapath and the alignment of bits is preserved. Thus, the layout of the ROM in silicon is dense, efficient, and matches the width of the rest of the floating-point unit. Polynomial approximation: don't use a Taylor series Now I'll move from the hardware to the constants. If you look at the constant ROM contents in the appendix, you may notice that many constants are close to reciprocals or reciprocal factorials, but don't quite match. For instance, one constant is 0.1111111089, which is close to 1/9, but visibly wrong. Another constant is almost 1/13! (factorial) but wrong by 0.1%. What's going on? The Pentium uses polynomials to approximate transcendental functions (sine, cosine, tangent, arctangent, and base-2 powers and logarithms). Intel's earlier floating-point units, from the 8087 to the 486, used an algorithm called CORDIC that generated results a bit at a time. However, the Pentium takes advantage of its fast multiplier and larger ROM and uses polynomials instead, computing results two to three times faster than the 486 algorithm. You may recall from calculus that a Taylor series polynomial approximates a function near a point (typically 0). For example, the equation below gives the Taylor series for sine. Using the five terms shown above generates a function that looks indistinguishable from sine in the graph below. However, it turns out that this approximation has too much error to be useful. Plot of the sine function and the Taylor series approximation. The problem is that a Taylor series is very accurate near 0, but the error soars near the edges of the argument range, as shown in the graph on the left below. When implementing a function, we want the function to be accurate everywhere, not just close to 0, so the Taylor series isn't good enough. The absolute error for a Taylor-series approximation to sine (5 terms), over two different argument ranges. One improvement is called range reduction: shrinking the argument to a smaller range so you're in the accurate flat part.6 The graph on the right looks at the Taylor series over the smaller range [-1/32, 1/32]. This decreases the error dramatically, by about 22 orders of magnitude (note the scale change). However, the error still shoots up at the edges of the range in exactly the same way. No matter how much you reduce the range, there is almost no error in the middle, but the edges have a lot of error.7 How can we get rid of the error near the edges? The trick is to tweak the coefficients of the Taylor series in a special way that will increase the error in the middle, but decrease the error at the edges by much more. Since we want to minimize the maximum error across the range (called minimax), this tradeoff is beneficial. Specifically, the coefficients can be optimized by a process called the Remez algorithm.8 As shown below, changing the coefficients by less than 1% dramatically improves the accuracy. The optimized function (blue) has much lower error over the full range, so it is a much better approximation than the Taylor series (orange). Comparison of the absolute error from the Taylor series and a Remez-optimized polynomial, both with maximum term x9. This Remez polynomial is not one from the Pentium. To summarize, a Taylor series is useful in calculus, but shouldn't be used to approximate a function. You get a much better approximation by modifying the coefficients very slightly with the Remez algorithm. This explains why the coefficients in the ROM almost, but not quite, match a Taylor series. Arctan I'll now look at the Pentium's constants for different transcendental functions. The constant ROM contains coefficients for two arctan polynomials, one for single precision and one for double precision. These polynomials almost match the Taylor series, but have been modified for accuracy. The ROM also holds the values for arctan(1/32) through arctan(32/32); the range reduction process uses these constants with a trig identity to reduce the argument range to [-1/64, 1/64].9 You can see the arctan constants in the Appendix. The graph below shows the error for the Pentium's arctan polynomial (blue) versus the Taylor series of the same length (orange). The Pentium's polynomial is superior due to the Remez optimization. Although the Taylor series polynomial is much flatter in the middle, the error soars near the boundary. The Pentium's polynomial wiggles more but it maintains a low error across the whole range. The error in the Pentium polynomial blows up outside this range, but that doesn't matter. Comparison of the Pentium's double-precision arctan polynomial to the Taylor series. Trig functions Sine and cosine each have two polynomial implementations, one with 4 terms in the ROM and one with 6 terms in the ROM. (Note that coefficients of 1 are not stored in the ROM.) The constant table also holds 16 constants such as sin(36/64) and cos(18/64) that are used for argument range reduction.10 The Pentium computes tangent by dividing the sine by the cosine. I'm not showing a graph because the Pentium's error came out worse than the Taylor series, so either I have an error in a coefficient or I'm doing something wrong. Exponential The Pentium has an instruction to compute a power of two.11 There are two sets of polynomial coefficients for exponential, one with 6 terms in the ROM and one with 11 terms in the ROM. Curiously, the polynomials in the ROM compute ex, not 2x. Thus, the Pentium must scale the argument by ln(2), a constant that is in the ROM. The error graph below shows the advantage of the Pentium's polynomial over the Taylor series polynomial. The Pentium's 6-term exponential polynomial, compared with the Taylor series. The polynomial handles the narrow argument range [-1/128, 1/128]. Observe that when computing a power of 2 in binary, exponentiating the integer part of the argument is trivial, since it becomes the result's exponent. Thus, the function only needs to handle the range [1, 2]. For range reduction, the constant ROM holds 64 values of the form 2n/128-1. To reduce the range from [1, 2] to [-1/128, 1/128], the closest n/128 is subtracted from the argument and then the result is multiplied by the corresponding constant in the ROM. The constants are spaced irregularly, presumably for accuracy; some are in steps of 4/128 and others are in steps of 2/128. Logarithm The Pentium can compute base-2 logarithms. The constant ROM has 9 coefficients, presumably for the logarithm polynomial (or polynomials), but I can't form a useful polynomial out of them.12 Unlike the other polynomials, this polynomial doesn't resemble the corresponding Taylor series. The ROM also has 64 constants for range reduction: log2(1+n/64) for odd n from 1 to 63. The unusual feature of these constants is that each constant is split into two pieces to increase the bits of accuracy: the top part has 40 bits of accuracy and the bottom part has 67 bits of accuracy, providing a 107-bit constant in total. The extra bits are required because logarithms are hard to compute accurately. Other constants The x87 floating-point instruction set provides direct access to a handful of constants—0, 1, pi, log2(10), log2(e), log10(2), and loge(2)—so these constants are stored in the ROM. (These logs are useful for changing the base for logs and exponentials.) The ROM holds other constants for internal use by the floating-point unit such as -1, 2, 7/8, 9/8, pi/2, pi/4, and 2log2(e). The ROM also holds bitmasks for extracting part of a word, for instance accessing 4-bit BCD digits in a word. Although I can interpret most of the values, there are a few mysteries such as a mask with the inscrutable value 0x5c3bd5191b525a249. The ROM has 34 unused entries at the end; these entries hold words that include the descriptive hex value 0xbad. How I examined the ROM To analyze the Pentium, I removed the metal and oxide layers with various chemicals (sulfuric acid, phosphoric acid, Whink). (I later discovered that simply sanding the die works surprisingly well.) Next, I took many photos of the ROM with a microscope. The feature size of this Pentium is 800 nm, just slightly larger than visible light (380-700 nm). Thus, the die can be examined under an optical microscope, but it is getting close to the limits. To determine the ROM contents, I tediously went through the ROM images, examining each of the 26144 bits and marking each transistor. After figuring out the ROM format, I wrote programs to combine simple functions in many different combinations to determine the mathematical expression such as arctan(19/32) or log2(10). Because the polynomial constants are optimized and my ROM data has bit errors, my program needed checks for inexact matches, both numerically and bitwise. Finally, I had to determine how the constants would be used in algorithms. Conclusions By examining the Pentium's floating-point ROM under a microscope, it is possible to extract the 304 constants stored in the ROM. I was able to determine the meaning of most of these constants and deduce some of the floating-point algorithms used by the Pentium. These constants illustrate how polynomials can efficiently compute transcendental functions. Although Taylor series polynomials are well known, they are surprisingly inaccurate and should be avoided. Minor changes to the coefficients through the Remez algorithm, however, yield much better polynomials. In a previous article, I examined the floating-point constants stored in the 8087 coprocessor. The Pentium has 304 constants in the Pentium, compared to just 42 in the 8087, supporting more efficient algorithms. Moreover, the 8087 was an external floating-point unit, while the Pentium's floating-point unit is part of the processor. The changes between the 8087 (1980, 65,000 transistors) and the Pentium (1993, 3.1 million transistors) are due to the exponential improvements in transistor count, as described by Moore's Law. I plan to write more about the Pentium so follow me on Bluesky (@righto.com) or RSS for updates. (I'm no longer on Twitter.) I've also written about the Pentium division bug and the Pentium Navajo rug. Thanks to CuriousMarc for microscope help. Appendix: The constant ROM The table below lists the 304 constants in the Pentium's floating-point ROM. The first four columns show the values stored in the ROM: the exponent, the sign bit, the flag bit, and the significand. To avoid negative exponents, exponents are stored with the constant 0x0ffff added. For example, the value 0x0fffe represents an exponent of -1, while 0x10000 represents an exponent of 1. The constant's approximate decimal value is in the "value" column. Special-purpose values are colored. Specifically, "normal" numbers are in black. Constants with an exponent of all 0's are in blue, constants with an exponent of all 1's are in red, constants with an unusually large or small exponent are in green; these appear to be bitmasks rather than numbers. Unused entries are in gray. Inexact constants (due to Remez optimization) are represented with the approximation symbol "≈". This information is from my reverse engineering, so there will be a few errors. expSFsignificandvaluemeaning 0 00000 0 0 07878787878787878 BCD mask by 4's 1 00000 0 0 007f807f807f807f8 BCD mask by 8's 2 00000 0 0 00007fff80007fff8 BCD mask by 16's 3 00000 0 0 000000007fffffff8 BCD mask by 32's 4 00000 0 0 78000000000000000 4-bit mask 5 00000 0 0 18000000000000000 2-bit mask 6 00000 0 0 27000000000000000 ? 7 00000 0 0 363c0000000000000 ? 8 00000 0 0 3e8287c0000000000 ? 9 00000 0 0 470de4df820000000 ? 10 00000 0 0 5c3bd5191b525a249 ? 11 00000 0 0 00000000000000007 3-bit mask 12 1ffff 1 1 7ffffffffffffffff all 1's 13 00000 0 0 0000007ffffffffff 43-bit mask 14 00000 0 0 00000000000003fff 14-bit mask 15 00000 0 0 00000000000000000 all 0's 16 0ffff 0 0 40000000000000000  1 1 17 10000 0 0 6a4d3c25e68dc57f2  3.3219280949 log2(10) 18 0ffff 0 0 5c551d94ae0bf85de  1.4426950409 log2(e) 19 10000 0 0 6487ed5110b4611a6  3.1415926536 pi 20 0ffff 0 0 6487ed5110b4611a6  1.5707963268 pi/2 21 0fffe 0 0 6487ed5110b4611a6  0.7853981634 pi/4 22 0fffd 0 0 4d104d427de7fbcc5  0.3010299957 log10(2) 23 0fffe 0 0 58b90bfbe8e7bcd5f  0.6931471806 ln(2) 24 1ffff 0 0 40000000000000000 ? 25 0bfc0 0 0 40000000000000000 ? 26 1ffff 1 0 60000000000000000 ? 27 0ffff 1 0 40000000000000000 -1 -1 28 10000 0 0 40000000000000000  2 2 29 00000 0 0 00000000000000001 low bit 30 00000 0 0 00000000000000000 all 0's 31 00001 0 0 00000000000000000 single exponent bit 32 0fffe 0 0 58b90bfbe8e7bcd5e  0.6931471806 ln(2) 33 0fffe 0 0 40000000000000000  0.5 1/2! (exp Taylor series) 34 0fffc 0 0 5555555555555584f  0.1666666667 ≈1/3! 35 0fffa 0 0 555555555397fffd4  0.0416666667 ≈1/4! 36 0fff8 0 0 444444444250ced0c  0.0083333333 ≈1/5! 37 0fff5 0 0 5b05c3dd3901cea50  0.0013888934 ≈1/6! 38 0fff2 0 0 6806988938f4f2318  0.0001984134 ≈1/7! 39 0fffe 0 0 40000000000000000  0.5 1/2! (exp Taylor series) 40 0fffc 0 0 5555555555555558e  0.1666666667 ≈1/3! 41 0fffa 0 0 5555555555555558b  0.0416666667 ≈1/4! 42 0fff8 0 0 444444444443db621  0.0083333333 ≈1/5! 43 0fff5 0 0 5b05b05b05afd42f4  0.0013888889 ≈1/6! 44 0fff2 0 0 68068068163b44194  0.0001984127 ≈1/7! 45 0ffef 0 0 6806806815d1b6d8a  0.0000248016 ≈1/8! 46 0ffec 0 0 5c778d8e0384c73ab  2.755731e-06 ≈1/9! 47 0ffe9 0 0 49f93e0ef41d6086b  2.755731e-07 ≈1/10! 48 0ffe5 0 0 6ba8b65b40f9c0ce8  2.506632e-08 ≈1/11! 49 0ffe2 0 0 47c5b695d0d1289a8  2.088849e-09 ≈1/12! 50 0fffd 0 0 6dfb23c651a2ef221  0.4296133384 266/128-1 51 0fffd 0 0 75feb564267c8bf6f  0.4609177942 270/128-1 52 0fffd 0 0 7e2f336cf4e62105d  0.4929077283 274/128-1 53 0fffe 0 0 4346ccda249764072  0.5255981507 278/128-1 54 0fffe 0 0 478d74c8abb9b15cc  0.5590044002 282/128-1 55 0fffe 0 0 4bec14fef2727c5cf  0.5931421513 286/128-1 56 0fffe 0 0 506333daef2b2594d  0.6280274219 290/128-1 57 0fffe 0 0 54f35aabcfedfa1f6  0.6636765803 294/128-1 58 0fffe 0 0 599d15c278afd7b60  0.7001063537 298/128-1 59 0fffe 0 0 5e60f4825e0e9123e  0.7373338353 2102/128-1 60 0fffe 0 0 633f8972be8a5a511  0.7753764925 2106/128-1 61 0fffe 0 0 68396a503c4bdc688  0.8142521755 2110/128-1 62 0fffe 0 0 6d4f301ed9942b846  0.8539791251 2114/128-1 63 0fffe 0 0 7281773c59ffb139f  0.8945759816 2118/128-1 64 0fffe 0 0 77d0df730ad13bb90  0.9360617935 2122/128-1 65 0fffe 0 0 7d3e0c0cf486c1748  0.9784560264 2126/128-1 66 0fffc 0 0 642e1f899b0626a74  0.1956643920 233/128-1 67 0fffc 0 0 6ad8abf253fe1928c  0.2086843236 235/128-1 68 0fffc 0 0 7195cda0bb0cb0b54  0.2218460330 237/128-1 69 0fffc 0 0 7865b862751c90800  0.2351510639 239/128-1 70 0fffc 0 0 7f48a09590037417f  0.2486009772 241/128-1 71 0fffd 0 0 431f5d950a896dc70  0.2621973504 243/128-1 72 0fffd 0 0 46a41ed1d00577251  0.2759417784 245/128-1 73 0fffd 0 0 4a32af0d7d3de672e  0.2898358734 247/128-1 74 0fffd 0 0 4dcb299fddd0d63b3  0.3038812652 249/128-1 75 0fffd 0 0 516daa2cf6641c113  0.3180796013 251/128-1 76 0fffd 0 0 551a4ca5d920ec52f  0.3324325471 253/128-1 77 0fffd 0 0 58d12d497c7fd252c  0.3469417862 255/128-1 78 0fffd 0 0 5c9268a5946b701c5  0.3616090206 257/128-1 79 0fffd 0 0 605e1b976dc08b077  0.3764359708 259/128-1 80 0fffd 0 0 6434634ccc31fc770  0.3914243758 261/128-1 81 0fffd 0 0 68155d44ca973081c  0.4065759938 263/128-1 82 0fffd 1 0 4cee3bed56eedb76c -0.3005101637 2-66/128-1 83 0fffd 1 0 50c4875296f5bc8b2 -0.3154987885 2-70/128-1 84 0fffd 1 0 5485c64a56c12cc8a -0.3301662380 2-74/128-1 85 0fffd 1 0 58326c4b169aca966 -0.3445193942 2-78/128-1 86 0fffd 1 0 5bcaea51f6197f61f -0.3585649920 2-82/128-1 87 0fffd 1 0 5f4faef0468eb03de -0.3723096215 2-86/128-1 88 0fffd 1 0 62c12658d30048af2 -0.3857597319 2-90/128-1 89 0fffd 1 0 661fba6cdf48059b2 -0.3989216343 2-94/128-1 90 0fffd 1 0 696bd2c8dfe7a5ffb -0.4118015042 2-98/128-1 91 0fffd 1 0 6ca5d4d0ec1916d43 -0.4244053850 2-102/128-1 92 0fffd 1 0 6fce23bceb994e239 -0.4367391907 2-106/128-1 93 0fffd 1 0 72e520a481a4561a5 -0.4488087083 2-110/128-1 94 0fffd 1 0 75eb2a8ab6910265f -0.4606196011 2-114/128-1 95 0fffd 1 0 78e09e696172efefc -0.4721774108 2-118/128-1 96 0fffd 1 0 7bc5d73c5321bfb9e -0.4834875605 2-122/128-1 97 0fffd 1 0 7e9b2e0c43fcf88c8 -0.4945553570 2-126/128-1 98 0fffc 1 0 53c94402c0c863f24 -0.1636449102 2-33/128-1 99 0fffc 1 0 58661eccf4ca790d2 -0.1726541162 2-35/128-1 100 0fffc 1 0 5cf6413b5d2cca73f -0.1815662751 2-37/128-1 101 0fffc 1 0 6179ce61cdcdce7db -0.1903824324 2-39/128-1 102 0fffc 1 0 65f0e8f35f84645cf -0.1991036222 2-41/128-1 103 0fffc 1 0 6a5bb3437adf1164b -0.2077308674 2-43/128-1 104 0fffc 1 0 6eba4f46e003a775a -0.2162651800 2-45/128-1 105 0fffc 1 0 730cde94abb7410d5 -0.2247075612 2-47/128-1 106 0fffc 1 0 775382675996699ad -0.2330590011 2-49/128-1 107 0fffc 1 0 7b8e5b9dc385331ad -0.2413204794 2-51/128-1 108 0fffc 1 0 7fbd8abc1e5ee49f2 -0.2494929652 2-53/128-1 109 0fffd 1 0 41f097f679f66c1db -0.2575774171 2-55/128-1 110 0fffd 1 0 43fcb5810d1604f37 -0.2655747833 2-57/128-1 111 0fffd 1 0 46032dbad3f462152 -0.2734860021 2-59/128-1 112 0fffd 1 0 48041035735be183c -0.2813120013 2-61/128-1 113 0fffd 1 0 49ff6c57a12a08945 -0.2890536989 2-63/128-1 114 0fffd 1 0 555555555555535f0 -0.3333333333 ≈-1/3 (arctan Taylor series) 115 0fffc 0 0 6666666664208b016  0.2 ≈ 1/5 116 0fffc 1 0 492491e0653ac37b8 -0.1428571307 ≈-1/7 117 0fffb 0 0 71b83f4133889b2f0  0.1110544094 ≈ 1/9 118 0fffd 1 0 55555555555555543 -0.3333333333 ≈-1/3 (arctan Taylor series) 119 0fffc 0 0 66666666666616b73  0.2 ≈ 1/5 120 0fffc 1 0 4924924920fca4493 -0.1428571429 ≈-1/7 121 0fffb 0 0 71c71c4be6f662c91  0.1111111089 ≈ 1/9 122 0fffb 1 0 5d16e0bde0b12eee8 -0.0909075848 ≈-1/11 123 0fffb 0 0 4e403be3e3c725aa0  0.0764169081 ≈ 1/13 124 00000 0 0 40000000000000000 single bit mask 125 0fff9 0 0 7ff556eea5d892a14  0.0312398334 arctan(1/32) 126 0fffa 0 0 7fd56edcb3f7a71b6  0.0624188100 arctan(2/32) 127 0fffb 0 0 5fb860980bc43a305  0.0934767812 arctan(3/32) 128 0fffb 0 0 7f56ea6ab0bdb7196  0.1243549945 arctan(4/32) 129 0fffc 0 0 4f5bbba31989b161a  0.1549967419 arctan(5/32) 130 0fffc 0 0 5ee5ed2f396c089a4  0.1853479500 arctan(6/32) 131 0fffc 0 0 6e435d4a498288118  0.2153576997 arctan(7/32) 132 0fffc 0 0 7d6dd7e4b203758ab  0.2449786631 arctan(8/32) 133 0fffd 0 0 462fd68c2fc5e0986  0.2741674511 arctan(9/32) 134 0fffd 0 0 4d89dcdc1faf2f34e  0.3028848684 arctan(10/32) 135 0fffd 0 0 54c2b6654735276d5  0.3310960767 arctan(11/32) 136 0fffd 0 0 5bd86507937bc239c  0.3587706703 arctan(12/32) 137 0fffd 0 0 62c934e5286c95b6d  0.3858826694 arctan(13/32) 138 0fffd 0 0 6993bb0f308ff2db2  0.4124104416 arctan(14/32) 139 0fffd 0 0 7036d3253b27be33e  0.4383365599 arctan(15/32) 140 0fffd 0 0 76b19c1586ed3da2b  0.4636476090 arctan(16/32) 141 0fffd 0 0 7d03742d50505f2e3  0.4883339511 arctan(17/32) 142 0fffe 0 0 4195fa536cc33f152  0.5123894603 arctan(18/32) 143 0fffe 0 0 4495766fef4aa3da8  0.5358112380 arctan(19/32) 144 0fffe 0 0 47802eaf7bfacfcdb  0.5585993153 arctan(20/32) 145 0fffe 0 0 4a563964c238c37b1  0.5807563536 arctan(21/32) 146 0fffe 0 0 4d17c07338deed102  0.6022873461 arctan(22/32) 147 0fffe 0 0 4fc4fee27a5bd0f68  0.6231993299 arctan(23/32) 148 0fffe 0 0 525e3e8c9a7b84921  0.6435011088 arctan(24/32) 149 0fffe 0 0 54e3d5ee24187ae45  0.6632029927 arctan(25/32) 150 0fffe 0 0 5756261c5a6c60401  0.6823165549 arctan(26/32) 151 0fffe 0 0 59b598e48f821b48b  0.7008544079 arctan(27/32) 152 0fffe 0 0 5c029f15e118cf39e  0.7188299996 arctan(28/32) 153 0fffe 0 0 5e3daef574c579407  0.7362574290 arctan(29/32) 154 0fffe 0 0 606742dc562933204  0.7531512810 arctan(30/32) 155 0fffe 0 0 627fd7fd5fc7deaa4  0.7695264804 arctan(31/32) 156 0fffe 0 0 6487ed5110b4611a6  0.7853981634 arctan(32/32) 157 0fffc 1 0 55555555555555555 -0.1666666667 ≈-1/3! (sin Taylor series) 158 0fff8 0 0 44444444444443e35  0.0083333333 ≈ 1/5! 159 0fff2 1 0 6806806806773c774 -0.0001984127 ≈-1/7! 160 0ffec 0 0 5c778e94f50956d70  2.755732e-06 ≈ 1/9! 161 0ffe5 1 0 6b991122efa0532f0 -2.505209e-08 ≈-1/11! 162 0ffde 0 0 58303f02614d5e4d8  1.604139e-10 ≈ 1/13! 163 0fffd 1 0 7fffffffffffffffe -0.5 ≈-1/2! (cos Taylor series) 164 0fffa 0 0 55555555555554277  0.0416666667 ≈ 1/4! 165 0fff5 1 0 5b05b05b05a18a1ba -0.0013888889 ≈-1/6! 166 0ffef 0 0 680680675b559f2cf  0.0000248016 ≈ 1/8! 167 0ffe9 1 0 49f93af61f5349300 -2.755730e-07 ≈-1/10! 168 0ffe2 0 0 47a4f2483514c1af8  2.085124e-09 ≈ 1/12! 169 0fffc 1 0 55555555555555445 -0.1666666667 ≈-1/3! (sin Taylor series) 170 0fff8 0 0 44444444443a3fdb6  0.0083333333 ≈ 1/5! 171 0fff2 1 0 68068060b2044e9ae -0.0001984127 ≈-1/7! 172 0ffec 0 0 5d75716e60f321240  2.785288e-06 ≈ 1/9! 173 0fffd 1 0 7fffffffffffffa28 -0.5 ≈-1/2! (cos Taylor series) 174 0fffa 0 0 555555555539cfae6  0.0416666667 ≈ 1/4! 175 0fff5 1 0 5b05b050f31b2e713 -0.0013888889 ≈-1/6! 176 0ffef 0 0 6803988d56e3bff10  0.0000247989 ≈ 1/8! 177 0fffe 0 0 44434312da70edd92  0.5333026735 sin(36/64) 178 0fffe 0 0 513ace073ce1aac13  0.6346070800 sin(44/64) 179 0fffe 0 0 5cedda037a95df6ee  0.7260086553 sin(52/64) 180 0fffe 0 0 672daa6ef3992b586  0.8060811083 sin(60/64) 181 0fffd 0 0 470df5931ae1d9460  0.2775567516 sin(18/64) 182 0fffd 0 0 5646f27e8bd65cbe4  0.3370200690 sin(22/64) 183 0fffd 0 0 6529afa7d51b12963  0.3951673302 sin(26/64) 184 0fffd 0 0 73a74b8f52947b682  0.4517714715 sin(30/64) 185 0fffe 0 0 6c4741058a93188ef  0.8459244992 cos(36/64) 186 0fffe 0 0 62ec41e9772401864  0.7728350058 cos(44/64) 187 0fffe 0 0 5806149bd58f7d46d  0.6876855622 cos(52/64) 188 0fffe 0 0 4bc044c9908390c72  0.5918050751 cos(60/64) 189 0fffe 0 0 7af8853ddbbe9ffd0  0.9607092430 cos(18/64) 190 0fffe 0 0 7882fd26b35b03d34  0.9414974631 cos(22/64) 191 0fffe 0 0 7594fc1cf900fe89e  0.9186091558 cos(26/64) 192 0fffe 0 0 72316fe3386a10d5a  0.8921336994 cos(30/64) 193 0ffff 0 0 48000000000000000  1.125 9/8 194 0fffe 0 0 70000000000000000  0.875 7/8 195 0ffff 0 0 5c551d94ae0bf85de  1.4426950409 log2(e) 196 10000 0 0 5c551d94ae0bf85de  2.8853900818 2log2(e) 197 0fffb 0 0 7b1c2770e81287c11  0.1202245867 coefficients for log? 198 0fff9 0 0 49ddb14064a5d30bd  0.0180336880 199 0fff6 0 0 698879b87934f12e0  0.0032206148 200 0fffa 0 0 51ff4ffeb20ed1749  0.0400377512 201 0fff6 0 0 5e8cd07eb1827434a  0.0028854387 202 0fff3 0 0 40e54061b26dd6dc2  0.0002475567 203 0ffef 0 0 61008a69627c92fb9  0.0000231271 204 0ffec 0 0 4c41e6ced287a2468  2.272648e-06 205 0ffe8 0 0 7dadd4ea3c3fee620  2.340954e-07 206 0fff9 0 0 5b9e5a170b8000000  0.0223678130 log2(1+1/64) top bits 207 0fffb 0 0 43ace37e8a8000000  0.0660892054 log2(1+3/64) top bits 208 0fffb 0 0 6f210902b68000000  0.1085244568 log2(1+5/64) top bits 209 0fffc 0 0 4caba789e28000000  0.1497471195 log2(1+7/64) top bits 210 0fffc 0 0 6130af40bc0000000  0.1898245589 log2(1+9/64) top bits 211 0fffc 0 0 7527b930c98000000  0.2288186905 log2(1+11/64) top bits 212 0fffd 0 0 444c1f6b4c0000000  0.2667865407 log2(1+13/64) top bits 213 0fffd 0 0 4dc4933a930000000  0.3037807482 log2(1+15/64) top bits 214 0fffd 0 0 570068e7ef8000000  0.3398500029 log2(1+17/64) top bits 215 0fffd 0 0 6002958c588000000  0.3750394313 log2(1+19/64) top bits 216 0fffd 0 0 68cdd829fd8000000  0.4093909361 log2(1+21/64) top bits 217 0fffd 0 0 7164beb4a58000000  0.4429434958 log2(1+23/64) top bits 218 0fffd 0 0 79c9aa879d8000000  0.4757334310 log2(1+25/64) top bits 219 0fffe 0 0 40ff6a2e5e8000000  0.5077946402 log2(1+27/64) top bits 220 0fffe 0 0 450327ea878000000  0.5391588111 log2(1+29/64) top bits 221 0fffe 0 0 48f107509c8000000  0.5698556083 log2(1+31/64) top bits 222 0fffe 0 0 4cc9f1aad28000000  0.5999128422 log2(1+33/64) top bits 223 0fffe 0 0 508ec1fa618000000  0.6293566201 log2(1+35/64) top bits 224 0fffe 0 0 5440461c228000000  0.6582114828 log2(1+37/64) top bits 225 0fffe 0 0 57df3fd0780000000  0.6865005272 log2(1+39/64) top bits 226 0fffe 0 0 5b6c65a9d88000000  0.7142455177 log2(1+41/64) top bits 227 0fffe 0 0 5ee863e4d40000000  0.7414669864 log2(1+43/64) top bits 228 0fffe 0 0 6253dd2c1b8000000  0.7681843248 log2(1+45/64) top bits 229 0fffe 0 0 65af6b4ab30000000  0.7944158664 log2(1+47/64) top bits 230 0fffe 0 0 68fb9fce388000000  0.8201789624 log2(1+49/64) top bits 231 0fffe 0 0 6c39049af30000000  0.8454900509 log2(1+51/64) top bits 232 0fffe 0 0 6f681c731a0000000  0.8703647196 log2(1+53/64) top bits 233 0fffe 0 0 72896372a50000000  0.8948177633 log2(1+55/64) top bits 234 0fffe 0 0 759d4f80cb8000000  0.9188632373 log2(1+57/64) top bits 235 0fffe 0 0 78a450b8380000000  0.9425145053 log2(1+59/64) top bits 236 0fffe 0 0 7b9ed1c6ce8000000  0.9657842847 log2(1+61/64) top bits 237 0fffe 0 0 7e8d3845df0000000  0.9886846868 log2(1+63/64) top bits 238 0ffd0 1 0 6eb3ac8ec0ef73f7b -1.229037e-14 log2(1+1/64) bottom bits 239 0ffcd 1 0 654c308b454666de9 -1.405787e-15 log2(1+3/64) bottom bits 240 0ffd2 0 0 5dd31d962d3728cbd  4.166652e-14 log2(1+5/64) bottom bits 241 0ffd3 0 0 70d0fa8f9603ad3a6  1.002010e-13 log2(1+7/64) bottom bits 242 0ffd1 0 0 765fba4491dcec753  2.628429e-14 log2(1+9/64) bottom bits 243 0ffd2 1 0 690370b4a9afdc5fb -4.663533e-14 log2(1+11/64) bottom bits 244 0ffd4 0 0 5bae584b82d3cad27  1.628582e-13 log2(1+13/64) bottom bits 245 0ffd4 0 0 6f66cc899b64303f7  1.978889e-13 log2(1+15/64) bottom bits 246 0ffd4 1 0 4bc302ffa76fafcba -1.345799e-13 log2(1+17/64) bottom bits 247 0ffd2 1 0 7579aa293ec16410a -5.216949e-14 log2(1+19/64) bottom bits 248 0ffcf 0 0 509d7c40d7979ec5b  4.475041e-15 log2(1+21/64) bottom bits 249 0ffd3 1 0 4a981811ab5110ccf -6.625289e-14 log2(1+23/64) bottom bits 250 0ffd4 1 0 596f9d730f685c776 -1.588702e-13 log2(1+25/64) bottom bits 251 0ffd4 1 0 680cc6bcb9bfa9853 -1.848298e-13 log2(1+27/64) bottom bits 252 0ffd4 0 0 5439e15a52a31604a  1.496156e-13 log2(1+29/64) bottom bits 253 0ffd4 0 0 7c8080ecc61a98814  2.211599e-13 log2(1+31/64) bottom bits 254 0ffd3 1 0 6b26f28dbf40b7bc0 -9.517022e-14 log2(1+33/64) bottom bits 255 0ffd5 0 0 554b383b0e8a55627  3.030245e-13 log2(1+35/64) bottom bits 256 0ffd5 0 0 47c6ef4a49bc59135  2.550034e-13 log2(1+37/64) bottom bits 257 0ffd5 0 0 4d75c658d602e66b0  2.751934e-13 log2(1+39/64) bottom bits 258 0ffd4 1 0 6b626820f81ca95da -1.907530e-13 log2(1+41/64) bottom bits 259 0ffd3 0 0 5c833d56efe4338fe  8.216774e-14 log2(1+43/64) bottom bits 260 0ffd5 0 0 7c5a0375163ec8d56  4.417857e-13 log2(1+45/64) bottom bits 261 0ffd5 1 0 5050809db75675c90 -2.853343e-13 log2(1+47/64) bottom bits 262 0ffd4 1 0 7e12f8672e55de96c -2.239526e-13 log2(1+49/64) bottom bits 263 0ffd5 0 0 435ebd376a70d849b  2.393466e-13 log2(1+51/64) bottom bits 264 0ffd2 1 0 6492ba487dfb264b3 -4.466345e-14 log2(1+53/64) bottom bits 265 0ffd5 1 0 674e5008e379faa7c -3.670163e-13 log2(1+55/64) bottom bits 266 0ffd5 0 0 5077f1f5f0cc82aab  2.858817e-13 log2(1+57/64) bottom bits 267 0ffd2 0 0 5007eeaa99f8ef14d  3.554090e-14 log2(1+59/64) bottom bits 268 0ffd5 0 0 4a83eb6e0f93f7a64  2.647316e-13 log2(1+61/64) bottom bits 269 0ffd3 0 0 466c525173dae9cf5  6.254831e-14 log2(1+63/64) bottom bits 270 0badf 0 1 40badfc0badfc0bad unused 271 0badf 0 1 40badfc0badfc0bad unused 272 0badf 0 1 40badfc0badfc0bad unused 273 0badf 0 1 40badfc0badfc0bad unused 274 0badf 0 1 40badfc0badfc0bad unused 275 0badf 0 1 40badfc0badfc0bad unused 276 0badf 0 1 40badfc0badfc0bad unused 277 0badf 0 1 40badfc0badfc0bad unused 278 0badf 0 1 40badfc0badfc0bad unused 279 0badf 0 1 40badfc0badfc0bad unused 280 0badf 0 1 40badfc0badfc0bad unused 281 0badf 0 1 40badfc0badfc0bad unused 282 0badf 0 1 40badfc0badfc0bad unused 283 0badf 0 1 40badfc0badfc0bad unused 284 0badf 0 1 40badfc0badfc0bad unused 285 0badf 0 1 40badfc0badfc0bad unused 286 0badf 0 1 40badfc0badfc0bad unused 287 0badf 0 1 40badfc0badfc0bad unused 288 0badf 0 1 40badfc0badfc0bad unused 289 0badf 0 1 40badfc0badfc0bad unused 290 0badf 0 1 40badfc0badfc0bad unused 291 0badf 0 1 40badfc0badfc0bad unused 292 0badf 0 1 40badfc0badfc0bad unused 293 0badf 0 1 40badfc0badfc0bad unused 294 0badf 0 1 40badfc0badfc0bad unused 295 0badf 0 1 40badfc0badfc0bad unused 296 0badf 0 1 40badfc0badfc0bad unused 297 0badf 0 1 40badfc0badfc0bad unused 298 0badf 0 1 40badfc0badfc0bad unused 299 0badf 0 1 40badfc0badfc0bad unused 300 0badf 0 1 40badfc0badfc0bad unused 301 0badf 0 1 40badfc0badfc0bad unused 302 0badf 0 1 40badfc0badfc0bad unused 303 0badf 0 1 40badfc0badfc0bad unused Notes and references In this blog post, I'm looking at the "P5" version of the original Pentium processor. It can be hard to keep all the Pentiums straight since "Pentium" became a brand name with multiple microarchitectures, lines, and products. The original Pentium (1993) was followed by the Pentium Pro (1995), Pentium II (1997), and so on. The original Pentium used the P5 microarchitecture, a superscalar microarchitecture that was advanced but still executed instruction in order like traditional microprocessors. The original Pentium went through several substantial revisions. The first Pentium product was the 80501 (codenamed P5), containing 3.1 million transistors. The power consumption of these chips was disappointing, so Intel improved the chip, producing the 80502, codenamed P54C. The P5 and P54C look almost the same on the die, but the P54C added circuitry for multiprocessing, boosting the transistor count to 3.3 million. The biggest change to the original Pentium was the Pentium MMX, with part number 80503 and codename P55C. The Pentium MMX added 57 vector processing instructions and had 4.5 million transistors. The floating-point unit was rearranged in the MMX, but the constants are probably the same. ↩ I don't know what the flag bit in the ROM indicates; I'm arbitrarily calling it a flag. My wild guess is that it indicates ROM entries that should be excluded from the checksum when testing the ROM. ↩ Internally, the significand has one integer bit and the remainder is the fraction, so the binary point (decimal point) is after the first bit. However, this is not the only way to represent the significand. The x87 80-bit floating-point format (double extended-precision) uses the same approach. However, the 32-bit (single-precision) and 64-bit (double-precision) formats drop the first bit and use an "implied" one bit. This gives you one more bit of significand "for free" since in normal cases the first significand bit will be 1. ↩ An unusual feature of the Pentium is that it uses bipolar NPN transistors along with CMOS circuits, a technology called BiCMOS. By adding a few extra processing steps to the regular CMOS manufacturing process, bipolar transistors could be created. The Pentium uses BiCMOS circuits extensively since they reduced signal delays by up to 35%. Intel also used BiCMOS for the Pentium Pro, Pentium II, Pentium III, and Xeon processors (but not the Pentium MMX). However, as chip voltages dropped, the benefit from bipolar transistors dropped too and BiCMOS was eventually abandoned. In the constant ROM, BiCMOS circuits improve the performance of the row selection circuitry. Each row select line is very long and is connected to hundreds of transistors, so the capacitive load is large. Because of the fast and powerful NPN transistor, a BiCMOS driver provides lower delay for higher loads than a regular CMOS driver. A typical BiCMOS inverter. From A 3.3V 0.6µm BiCMOS superscalar microprocessor. This BiCMOS logic is also called BiNMOS or BinMOS because the output has a bipolar transistor and an NMOS transistor. For more on BiCMOS circuits in the Pentium, see my article Standard cells: Looking at individual gates in the Pentium processor. ↩ The integer processing unit of the Pentium is constructed similarly, with horizontal functional units stacked to form the datapath. Each cell in the integer unit is much wider than a floating-point cell (64 µm vs 38.5 µm). However, the integer unit is just 32 bits wide, compared to 69 (more or less) for the floating-point unit, so the floating-point unit is wider overall. ↩ I don't like referring to the argument's range since a function's output is the range, while its input is the domain. But the term range reduction is what people use, so I'll go with it. ↩ There's a reason why the error curve looks similar even if you reduce the range. The error from the Taylor series is approximately the next term in the Taylor series, so in this case the error is roughly -x11/11! or O(x11). This shows why range reduction is so powerful: if you reduce the range by a factor of 2, you reduce the error by the enormous factor of 211. But this also shows why the error curve keeps its shape: the curve is still x11, just with different labels on the axes. ↩ The Pentium coefficients are probably obtained using the Remez algorithm; see Floating-Point Verification. The advantages of the Remez polynomial over the Taylor series are discussed in Better Function Approximations: Taylor vs. Remez. A description of Remez's algorithm is in Elementary Functions: Algorithms and Implementation, which has other relevant information on polynomial approximation and range reduction. For more on polynomial approximations, see Numerically Computing the Exponential Function with Polynomial Approximations and The Eight Useful Polynomial Approximations of Sinf(3), The Remez polynomial in the sine graph was generated by lolremez, a useful tool. The specific polynomial is: 9.9997938808335731e-1 ⋅ x - 1.6662438518867169e-1 ⋅ x3 + 8.3089850302282266e-3 ⋅ x5 - 1.9264997445395096e-4 ⋅ x7 + 2.1478735041839789e-6 ⋅ x9 The graph below shows the error for this polynomial. Note that the error oscillates between an upper bound and a lower bound. This is the typical appearance of a Remez polynomial. In contrast, a Taylor series will have almost no error in the middle and shoot up at the edges. This Remez polynomial was optimized for the range [-π,π]; the error explodes outside that range. The key point is that the Remez polynomial distributes the error inside the range. This minimizes the maximum error (minimax). ↩ Error from a Remez-optimized polynomial for sine. I think the arctan argument is range-reduced to the range [-1/64, 1/64]. This can be accomplished with the trig identity arctan(x) = arctan((x-c)/(1+xc)) + arctan(c). The idea is that c is selected to be the value of the form n/32 closest to x. As a result, x-c will be in the desired range and the first arctan can be computed with the polynomial. The other term, arctan(c), is obtained from the lookup table in the ROM. The FPATAN (partial arctangent) instruction takes two arguments, x and y, and returns atan(y/x); this simplifies handling planar coordinates. In this case, the trig identity becomes arcan(y/x) = arctan((y-tx)/(x+ty)) + arctan c. The division operation can trigger the FDIV bug in some cases; see Computational Aspects of the Pentium Affair. ↩ The Pentium has several trig instructions: FSIN, FCOS, and FSINCOS return the sine, cosine, or both (which is almost as fast as computing either). FPTAN returns the "partial tangent" consisting of two numbers that must be divided to yield the tangent. (This was due to limitations in the original 8087 coprocessor.) The Pentium returns the tangent as the first number and the constant 1 as the second number, keeping the semantics of FPTAN while being more convenient. The range reduction is probably based on the trig identity sin(a+b) = sin(a)cos(b)+cos(a)sin(b). To compute sin(x), select b as the closest constant in the lookup table, n/64, and then generate a=x-b. The value a will be range-reduced, so sin(a) can be computed from the polynomial. The terms sin(b) and cos(b) are available from the lookup table. The desired value sin(x) can then be computed with multiplications and addition by using the trig identity. Cosine can be computed similarly. Note that cos(a+b) =cos(a)cos(b)-sin(a)sin(b); the terms on the right are the same as for sin(a+b), just combined differently. Thus, once the terms on the right have been computed, they can be combined to generate sine, cosine, or both. The Pentium computes the tangent by dividing the sine by the cosine. This can trigger the FDIV division bug; see Computational Aspects of the Pentium Affair. Also see Agner Fog's Instruction Timings; the timings for the various operations give clues as to how they are computed. For instance, FPTAN takes longer than FSINCOS because the tangent is generated by dividing the sine by the cosine. ↩ For exponentials, the F2XM1 instruction computes 2x-1; subtracting 1 improves accuracy. Specifically, 2x is close to 1 for the common case when x is close to 0, so subtracting 1 as a separate operation causes you to lose most of the bits of accuracy due to cancellation. On the other hand, if you want 2x, explicitly adding 1 doesn't harm accuracy. This is an example of how the floating-point instructions are carefully designed to preserve accuracy. For details, see the book The 8087 Primer by the architects of the 8086 processor and the 8087 coprocessor. ↩ The Pentium has base-two logarithm instructions FYL2X and FYL2XP1. The FYL2X instruction computes y log2(x) and the FYL2XP1 instruction computes y log2(x+1) The instructions include a multiplication because most logarithm operations will need to multiply to change the base; performing the multiply with internal precision increases the accuracy. The "plus-one" instruction improves accuracy for arguments close to 1, such as interest calculations. My hypothesis for range reduction is that the input argument is scaled to fall between 1 and 2. (Taking the log of the exponent part of the argument is trivial since the base-2 log of a base-2 power is simply the exponent.) The argument can then be divided by the largest constant 1+n/64 less than the argument. This will reduce the argument to the range [1, 1+1/32]. The log polynomial can be evaluated on the reduced argument. Finally, the ROM constant for log2(1+n/64) is added to counteract the division. The constant is split into two parts for greater accuracy. It took me a long time to figure out the log constants because they were split. The upper-part constants appeared to be pointlessly inaccurate since the bottom 27 bits are zeroed out. The lower-part constants appeared to be miniscule semi-random numbers around ±10-13. Eventually, I figured out that the trick was to combine the constants. I haven't figured out how the coefficients form the logarithm polynomial. The Taylor series for logarithm has coefficients ±1/n, but the coefficients in the ROM are completely different from that. It's not obvious how to make the coefficients into a polynomial since the powers: does the first term go with x1, x2, or something else? And coefficients of 1 aren't stored in the table. It could even be a ratio of polynomials. Moreover, I may have bit errors in the coefficients. In any case, I tried many formulas and couldn't come up with anything reasonable. ↩

In 1993, Intel released the high-performance Pentium processor, the start of the long-running Pentium line. The Pentium had many improvements over the previous processor, the Intel 486, including a faster floating-point division algorithm. A year later, Professor Nicely, a number theory professor, was researching reciprocals of twin prime numbers when he noticed a problem: his Pentium sometimes generated the wrong result when performing floating-point division. Intel considered this "an extremely minor technical problem", but much to Intel's surprise, the bug became a large media story. After weeks of criticism, mockery, and bad publicity, Intel agreed to replace everyone's faulty Pentium chips, costing the company $475 million. In this article, I discuss the Pentium's division algorithm, show exactly where the bug is on the Pentium chip, take a close look at the circuitry, and explain what went wrong. In brief, the division algorithm uses a lookup table. In 1994, Intel stated that the cause of the bug was that five entries were omitted from the table due to an error in a script. However, my analysis shows that 16 entries were omitted due to a mathematical mistake in the definition of the lookup table. Five of the missing entries trigger the bug— also called the FDIV bug after the floating-point division instruction "FDIV"—while 11 of the missing entries have no effect. This die photo of the Pentium shows the location of the FDIV bug. Click this image (or any other) for a larger version. Although Professor Nicely brought attention to the FDIV bug, he wasn't the first to find it. In May 1994, Intel's internal testing of the Pentium revealed that very rarely, floating-point division was slightly inaccurate.1 Since only one in 9 billion values caused the problem, Intel's view was that the problem was trivial: "This doesn't even qualify as an errata." Nonetheless, Intel quietly revised the Pentium circuitry to fix the problem. A few months later, in October, Nicely noticed erroneous results in his prime number computations.2 He soon determined that 1/824633702441 was wrong on three different Pentium computers, but his older computers gave the right answer. He called Intel tech support but was brushed off, so Nicely emailed a dozen computer magazines and individuals about the bug. One of the recipients was Andrew Schulman, author of "Undocumented DOS". He forwarded the email to Richard Smith, cofounder of a DOS software tools company. Smith posted the email on a Compuserve forum, a 1990s version of social media. A reporter for the journal Electronic Engineering Times spotted the Compuserve post and wrote about the Pentium bug in the November 7 issue: Intel fixes a Pentium FPU glitch. In the article, Intel explained that the bug was in a component of the chip called a PLA (Programmable Logic Array) that acted as a lookup table for the division operation. Intel had fixed the bug in the latest Pentiums and would replace faulty processors for concerned customers.3 The problem might have quietly ended here, except that Intel decided to restrict which customers could get a replacement. If a customer couldn't convince an Intel engineer that they needed the accuracy, they couldn't get a fixed Pentium. Users were irate to be stuck with faulty chips so they took their complaints to online groups such as comp.sys.intel. The controversy spilled over into the offline world on November 22 when CNN reported on the bug. Public awareness of the Pentium bug took off as newspapers wrote about the bug and Intel became a punchline on talk shows.4 The situation became intolerable for Intel on December 12 when IBM announced that it was stopping shipments of Pentium computers.5 On December 19, less than two months after Nicely first reported the bug, Intel gave in and announced that it would replace the flawed chips for all customers.6 This recall cost Intel $475 million (over a billion dollars in current dollars). Meanwhile, engineers and mathematicians were analyzing the bug, including Tim Coe, an engineer who had designed floating-point units.7 Remarkably, by studying the Pentium's bad divisions, Coe reverse-engineered the Pentium's division algorithm and determined why it went wrong. Coe and others wrote papers describing the mathematics behind the Pentium bug.8 But until now, nobody has shown how the bug is implemented in the physical chip itself. A quick explanation of floating point numbers At this point, I'll review a few important things about floating point numbers. A binary number can have a fractional part, similar to a decimal number. For instance, the binary number 11.1001 has four digits after the binary point. (The binary point "." is similar to the decimal point, but for a binary number.) The first digit after the binary point represents 1/2, the second represents 1/4, and so forth. Thus, 11.1001 corresponds to 3 + 1/2 + 1/16 = 3.5625. A "fixed point" number such as this can express a fractional value, but its range is limited. Floating point numbers, on the other hand, include very large numbers such as 6.02×1023 and very small numbers such as 1.055×10−34. In decimal, 6.02×1023 has a significand (or mantissa) of 6.02, multiplied by a power of 10 with an exponent of 23. In binary, a floating point number is represented similarly, with a significand and exponent, except the significand is multiplied by a power of 2 rather than 10. Computers have used floating point since the early days of computing, especially for scientific computing. For many years, different computers used incompatible formats for floating point numbers. Eventually, a standard arose when Intel developed the 8087 floating point coprocessor chip for use with the 8086/8088 processor. The characteristics of this chip became a standard (IEEE 754) in 1985.9 Subsequently, most computers, including the Pentium, implemented floating point numbers according to this standard. The result of a basic arithmetic operation is supposed to be accurate up to the last bit of the significand. Unfortunately, division on the Pentium was occasionally much, much worse. How SRT division works How does a computer perform division? The straightforward way is similar to grade-school long division, except in binary. That approach was used in the Intel 486 and earlier processors, but the process is slow, taking one clock cycle for each bit of the quotient. The Pentium uses a different approach called SRT, performing division in base four. Thus, SRT generates two bits of the quotient per step, rather than one, so division is twice as fast. I'll explain SRT in a hand-waving manner with a base-10 example; rigorous explanations are available elsewhere.10 The diagram below shows base-10 long division, with the important parts named. The dividend is divided by the divisor, yielding the quotient. In each step of the long division algorithm, you generate one more digit of the quotient. Then you multiply the divisor (1535) by the quotient digit (2) and subtract this from the dividend, leaving a partial remainder. You multiply the partial remainder by 10 and then repeat the process, generating a quotient digit and partial remainder at each step. The diagram below stops after two quotient digits, but you can keep going to get as much accuracy as desired. Base-10 division, naming the important parts. Note that division is more difficult than multiplication since there is no easy way to determine each quotient digit. You have to estimate a quotient digit, multiply it by the divisor, and then check if the quotient digit is correct. For example, you have to check carefully to see if 1535 goes into 4578 two times or three times. The SRT algorithm makes it easier to select the quotient digit through an unusual approach: it allows negative digits in the quotient. With this change, the quotient digit does not need to be exact. If you pick a quotient digit that is a bit too large, you can use a negative number for the next digit: this will counteract the too-large digit since the next divisor will be added rather than subtracted. The example below shows how this works. Suppose you picked 3 instead of 2 as the first quotient digit. Since 3 is too big, the partial remainder is negative (-261). In normal division, you'd need to try again with a different quotient digit. But with SRT, you keep going, using a negative digit (-1) for the quotient digit in the next step. At the end, the quotient with positive and negative digits can be converted to the standard form: 3×10-1 = 29, the same quotient as before. Base-10 division, using a negative quotient digit. The result is the same as the previous example. One nice thing about the SRT algorithm is that since the quotient digit only needs to be close, a lookup table can be used to select the quotient digit. Specifically, the partial remainder and divisor can be truncated to a few digits, making the lookup table a practical size. In this example, you could truncate 1535 and 4578 to 15 and 45, the table says that 15 goes into 45 three times, and you can use 3 as your quotient digit. Instead of base 10, the Pentium uses the SRT algorithm in base 4: groups of two bits. As a result, division on the Pentium is twice as fast as standard binary division. With base-4 SRT, each quotient digit can be -2, -1, 0, 1, or 2. Multiplying by any of these values is very easy in hardware since multiplying by 2 can be done by a bit shift. Base-4 SRT does not require quotient digits of -3 or 3; this is convenient since multiplying by 3 is somewhat difficult. To summarize, base-4 SRT is twice as fast as regular binary division, but it requires more hardware: a lookup table, circuitry to add or subtract multiples of 1 or 2, and circuitry to convert the quotient to the standard form. Structure of the Pentium's lookup table The purpose of the SRT lookup table is to provide the quotient digit. That is, the table takes the partial remainder p and the divisor d as inputs and provides an appropriate quotient digit. The Pentium's lookup table is the cause of the division bug, as was explained in 1994. The table was missing five entries; if the SRT algorithm accesses one of these missing entries, it generates an incorrect result. In this section, I'll discuss the structure of the lookup table and explain what went wrong. The Pentium's lookup table contains 2048 entries, as shown below. The table has five regions corresponding to the quotient digits +2, +1, 0, -1, and -2. Moreover, the upper and lower regions of the table are unused (due to the mathematics of SRT). The unused entries were filled with 0, which turns out to be very important. In particular, the five red entries need to contain +2 but were erroneously filled with 0. The 2048-entry lookup table used in the Pentium for division. The divisor is along the X-axis, from 1 to 2. The partial remainder is along the Y-axis, from -8 to 8. Click for a larger version. When the SRT algorithm uses the table, the partial remainder p and the divisor d are inputs. The divisor (scaled to fall between 1 and 2) provides the X coordinate into the table, while the partial remainder (between -8 and 8) provides the Y coordinate. The details of the table coordinates will be important, so I'll go into some detail. To select a cell, the divisor (X-axis) is truncated to a 5-bit binary value 1.dddd. (Since the first digit of the divisor is always 1, it is ignored for the table lookup.) The partial remainder (Y-axis) is truncated to a 7-bit signed binary value pppp.ppp. The 11 bits indexing into the table result in a table with 211 (2048) entries. The partial remainder is expressed in 2's complement, so values 0000.000 to 0111.111 are non-negative values from 0 to (almost) 8, while values 1000.000 to 1111.111 are negative values from -8 to (almost) 0. (To see the binary coordinates for the table, click on the image and zoom in.) The lookup table is implemented in a Programmable Logic Array (PLA) In this section, I'll explain how the lookup table is implemented in hardware in the Pentium. The lookup table has 2048 entries so it could be stored in a ROM with 2048 two-bit outputs.11 (The sign is not explicitly stored in the table because the quotient digit sign is the same as the partial remainder sign.) However, because the table is highly structured (and largely empty), the table can be stored more compactly in a structure called a Programmable Logic Array (PLA).12 By using a PLA, the Pentium stored the table in just 112 rows rather than 2048 rows, saving an enormous amount of space. Even so, the PLA is large enough on the chip that it is visible to the naked eye, if you squint a bit. Zooming in on the PLA and associated circuitry on the Pentium die. The idea of a PLA is to provide a dense and flexible way of implementing arbitrary logic functions. Any Boolean logic function can be expressed as a "sum-of-products", a collection of AND terms (products) that are OR'd together (summed). A PLA has a block of circuitry called the AND plane that generates the desired sum terms. The outputs of the AND plane are fed into a second block, the OR plane, which ORs the terms together. The AND plane and the OR plane are organized as grids. Each gridpoint can either have a transistor or not, defining the logic functions. The point is that by putting the appropriate pattern of transistors in the grids, you can create any function. For the division PLA, there are has 22 inputs (the 11 bits from the divisor and partial remainder indices, along with their complements) and two outputs, as shown below.13 A simplified diagram of the division PLA. A PLA is more compact than a ROM if the structure of the function allows it to be expressed with a small number of terms.14 One difficulty with a PLA is figuring out how to express the function with the minimum number of terms to make the PLA as small as possible. It turns out that this problem is NP-complete in general. Intel used a program called Espresso to generate compact PLAs using heuristics.15 The diagram below shows the division PLA in the Pentium. The PLA has 120 rows, split into two 60-row parts with support circuitry in the middle.16 The 11 table input bits go into the AND plane drivers in the middle, which produce the 22 inputs to the PLA (each table input and its complement). The outputs from the AND plane transistors go through output buffers and are fed into the OR plane. The outputs from the OR plane go through additional buffers and logic in the center, producing two output bits, indicating a ±1 or ±2 quotient. The image below shows the updated PLA that fixes the bug; the faulty PLA looks similar except the transistor pattern is different. In particular, the updated PLA has 46 unused rows at the bottom while the original, faulty PLA has 8 unused rows. The division PLA with the metal layers removed to show the silicon. This image shows the PLA in the updated Pentium, since that photo came out better. The image below shows part of the AND plane of the PLA. At each point in the grid, a transistor can be present or absent. The pattern of transistors in a row determines the logic term for that row. The vertical doped silicon lines (green) are connected to ground. The vertical polysilicon lines (red) are driven with the input bit pattern. If a polysilicon line crosses doped silicon, it forms a transistor (orange) that will pull that row to ground when activated.17 A metal line connects all the transistor rows in a row to produce the output; most of the metal has been removed, but some metal lines are visible at the right. Part of the AND plane in the fixed Pentium. I colored the first silicon and polysilicon lines green and red respectively. By carefully examining the PLA under a microscope, I extracted the pattern of transistors in the PLA grid. (This was somewhat tedious.) From the transistor pattern, I could determine the equations for each PLA row, and then generate the contents of the lookup table. Note that the transistors in the PLA don't directly map to the table contents (unlike a ROM). Thus, there is no specific place for transistors corresponding to the 5 missing table entries. The left-hand side of the PLA implements the OR planes (below). The OR plane determines if the row output produces a quotient of 1 or 2. The OR plane is oriented 90° relative to the AND plane: the inputs are horizontal polysilicon lines (red) while the output lines are vertical. As before, a transistor (orange) is formed where polysilicon crosses doped silicon. Curiously, each OR plane has four outputs, even though the PLA itself has two outputs.18 Part of the OR plane of the division PLA. I removed the metal layers to show the underlying silicon and polysilicon. I drew lines for ground and outputs, showing where the metal lines were. Next, I'll show exactly how the AND plane produces a term. For the division table, the inputs are the 7 partial remainder bits and 4 divisor bits, as explained earlier. I'll call the partial remainder bits p6p5p4p3.p2p1p0 and the divisor bits 1.d3d2d1d0. These 11 bits and their complements are fed vertically into the PLA as shown at the top of the diagram below. These lines are polysilicon, so they will form transistor gates, turning on the corresponding transistor when activated. The arrows at the bottom point to nine transistors in the first row. (It's tricky to tell if the polysilicon line passes next to doped silicon or over the silicon, so the transistors aren't always obvious.) Looking at the transistors and their inputs shows that the first term in the PLA is generated by p0p1p2p3p4'p5p6d1d2. The first row of the division PLA in a faulty Pentium. The diagram below is a closeup of the lookup table, showing how this PLA row assigns the value 1 to four table cells (dark blue). You can think of each term of the PLA as pattern-matching to a binary pattern that can include "don't care" values. The first PLA term (above) matches the pattern P=110.1111, D=x11x, where the "don't care" x values can be either 0 or 1. Since one PLA row can implement multiple table cells, the PLA is more efficient than a ROM; the PLA uses 112 rows, while a ROM would require 2048 rows. The first entry in the PLA assigns the value 1 to the four dark blue cells. Geometrically, you can think of each PLA term (row) as covering a rectangle or rectangles in the table. However, the rectangle can't be arbitrary, but must be aligned on a bit boundary. Note that each "bump" in the table boundary (magenta) requires a separate rectangle and thus a separate PLA row. (This will be important later.) One PLA row can generate a large rectangle, filling in many table cells at once, if the region happens to be aligned nicely. For instance, the third term in the PLA matches d=xxxx, p=11101xx. This single PLA row efficiently fills in 64 table cells as shown below, replacing the 64 rows that would be required in a ROM. The third entry in the PLA assigns the value 1 to the 64 dark blue cells. To summarize, the pattern of transistors in the PLA implements a set of equations, which define the contents of the table, setting the quotient to 1 or 2 as appropriate. Although the table has 2048 entries, the PLA represents the contents in just 112 rows. By carefully examining the transistor pattern, I determined the table contents in a faulty Pentium and a fixed Pentium. The mathematical bounds of the lookup table As shown earlier, the lookup table has regions corresponding to quotient digits of +2, +1, 0, -1, and -2. These regions have irregular, slanted shapes, defined by mathematical bounds. In this section, I'll explain these mathematical bounds since they are critical to understanding how the Pentium bug occurred. The essential step of the division algorithm is to divide the partial remainder p by the divisor d to get the quotient digit. The following diagram shows how p/d determines the quotient digit. The ratio p/d will define a point on the line at the top. (The point will be in the range [-8/3, 8/3] for mathematical reasons.) The point will fall into one of the five lines below, defining the quotient digit q. However, the five quotient regions overlap; if p/d is in one of the green segments, there are two possible quotient digits. The next part of the diagram illustrates how subtracting q*d from the partial remainder p shifts p/d into the middle, between -2/3 and 2/3. Finally, the result is multiplied by 4 (shifted left by two bits), expanding19 the interval back to [-8/3, 8/3], which is the same size as the original interval. The 8/3 bound may seem arbitrary, but the motivation is that it ensures tht the new interval is the same size as the original interval, so the process can be repeated. (The bounds are all thirds for algebraic reasons; the value 3 comes from base 4 minus 1.20) The input to a division step is processed, yielding the input to the next step. Note that the SRT algorithm has some redundancy, but cannot handle q values that are "too wrong". Specifically, if p/d is in a green region, then either of two q values can be selected. However, the algorithm cannot recover from a bad q value in general. The relevant case is that if q is supposed to be 2 but 0 is selected, the next partial remainder will be outside the interval and the algorithm can't recover. This is what causes the FDIV bug. The diagram below shows the structure of the SRT lookup table (also called the P-D table since the axes are p and d). Each bound in the diagram above turns into a line in the table. For instance, the green segment above with p/d between 4/3 and 5/3 turns into a green region in the table below with 4/3 d ≤ p ≤ 5/3 d. These slanted lines show the regions in which a particular quotient digit q can be used. The P-D table specifies the quotient digit for a partial remainder (Y-axis) and divisor (X-axis). The lookup table in the Pentium is based on the above table, quantized with a q value in each cell. However, there is one more constraint to discuss. Carry-save and carry-lookahead adders The Pentium's division circuitry uses a special circuit to perform addition and subtraction efficiently: the carry-save adder. One consequence of this adder is that each access to the lookup table may go to the cell just below the "right" cell. This is expected and should be fine, but in very rare and complicated circumstances, this behavior causes an access to one of the Pentium's five missing cells, triggering the division bug. In this section, I'll discuss why the division circuitry uses a carry-save adder, how the carry-save adder works, and how the carry-save adder triggers the FDIV bug. The problem with addition is that carries make addition slow. Consider calculating 99999+1 by hand. You'll start with 9+1=10, then carry the one, generating another carry, which generates another carry, and so forth, until you go through all the digits. Computer addition has the same problem. If you're adding, say, two 64-bit numbers, the low-order bits can generate a carry that then propagates through all 64 bits. The time for the carry signal to go through 64 layers of circuitry is significant and can limit CPU performance. As a result, CPUs use special circuits to make addition faster. The Pentium's division circuitry uses an unusual adder circuit called a carry-save adder to add (or subtract) the divisor and the partial remainder. A carry-save adder speeds up addition if you are performing a bunch of additions, as happens during division. The idea is that instead of adding a carry to each digit as it happens, you hold onto the carries in a separate word. As a decimal example, 499+222 would be 611 with carries 011; you don't carry the one to the second digit, but hold onto it. The next time you do an addition, you add in the carries you saved previously, and again save any new carries. The advantage of the carry-save adder is that the sum and carry at each digit position can be computed in parallel, which is fast. The disadvantage is that you need to do a slow addition at the end of the sequence of additions to add in the remaining carries to get the final answer. But if you're performing multiple additions (as for division), the carry-save adder is faster overall. The carry-save adder creates a problem for the lookup table. We need to use the partial remainder as an index into the lookup table. But the carry-save adder splits the partial remainder into two parts: the sum bits and the carry bits. To get the table index, we need to add the sum bits and carry bits together. Since this addition needs to happen for every step of the division, it seems like we're back to using a slow adder and the carry-save adder has just made things worse. The trick is that we only need 7 bits of the partial remainder for the table index, so we can use a different type of adder—a carry-lookahead adder—that calculates each carry in parallel using brute force logic. The logic in a carry-lookahead adder gets more and more complex for each bit so a carry-lookahead adder is impractical for large words, but it is practical for a 7-bit value. The photo below shows the carry-lookahead adder used by the divider. Curiously, the adder is an 8-bit adder but only 7 bits are used; perhaps the 8-bit adder was a standard logic block at Intel.21 I'll just give a quick summary of the adder here, and leave the details for another post. At the top, logic gates compute signals in parallel for each of the 8 pairs of inputs: sum, carry generate, and carry propagate. Next, the complex carry-lookahead logic determines in parallel if there will be a carry at each position. Finally, XOR gates apply the carry to each bit. The circuitry in the middle is used for testing; see the footnote.22 At the bottom, the drivers amplify control signals for various parts of the adder and send the PLA output to other parts of the chip.23 By counting the blocks of repeated circuitry, you can see which blocks are 8 bits wide, 11, bits wide, and so forth. The carry-lookahead logic is different for each bit, so there is no repeated structure. The carry-lookahead adder that feeds the lookup table. This block of circuitry is just above the PLA on the die. I removed the metal layers, so this photo shows the doped silicon (dark) and the polysilicon (faint gray). The carry-save and carry-lookahead adders may seem like implementation trivia, but they are a critical part of the FDIV bug because they change the constraints on the table. The cause is that the partial remainder is 64 bits,24 but the adder that computes the table index is 7 bits. Since the rest of the bits are truncated before the sum, the partial remainder sum for the table index can be slightly lower than the real partial remainder. Specifically, the table index can be one cell lower than the correct cell, an offset of 1/8. Recall the earlier diagram with diagonal lines separating the regions. Some (but not all) of these lines must be shifted down by 1/8 to account for the carry-save effect, but Intel made the wrong adjustment, which is the root cause of the FDIV error. (This effect was well-known at the time and mentioned in papers on SRT division, so Intel shouldn't have gotten it wrong.) An interesting thing about the FDIV bug is how extremely rare it is. With 5 bad table entries out of 2048, you'd expect erroneous divides to be very common. However, for complicated mathematical reasons involving the carry-save adder the missing table entries are almost never encountered: only about 1 in 9 billion random divisions will encounter a problem. To hit a missing table entry, you need an "unlucky" result from the carry-save adder multiple times in a row, making the odds similar to winning the lottery, if the lottery prize were a division error.25 What went wrong in the lookup table I consider the diagram below to be the "smoking gun" that explains how the FDIV bug happens: the top magenta line should be above the sloping black line, but it crosses the black line repeatedly. The magenta line carefully stays above the gray line, but that's the wrong line. In other words, Intel picked the wrong bounds line when defining the +2 region of the table. In this section, I'll explain why that causes the bug. The top half of the lookup table, explaining the root of the FDIV bug. The diagram is colored according to the quotient values stored in the Pentium's lookup table: yellow is +2, blue is +1, and white is 0, with magenta lines showing the boundaries between different values. The diagonal black lines are the mathematical constraints on the table, defining the region that must be +2, the region that can be +1 or +2, the region that must be +1, and so forth. For the table to be correct, each cell value in the table must satisfy these constraints. The middle magenta line is valid: it remains between the two black lines (the redundant +1 or +2 region), so all the cells that need to be +1 are +1 and all the cells that need to be +2 are +2, as required. Likewise, the bottom magenta line remains between the black lines. However, the top magenta line is faulty: it must remain above the top black line, but it crosses the black line. The consequence is that some cells that need to be +2 end up holding 0: these are the missing cells that caused the FDIV bug. Note that the top magenta line stays above the diagonal gray line while following it as closely as possible. If the gray line were the correct line, the table would be perfect. Unfortunately, Intel picked the wrong constraint line for the table's upper bound when the table was generated.26 But why are some diagonal lines lowered by 1/8 and other lines are not lowered? As explained in the previous section, as a consequence of the carry-save adder truncation, the table lookup may end up one cell lower than the actual p value would indicate, i.e. the p value for the table index is 1/8 lower than that actual value. Thus, both the correct cell and the cell below must satisfy the SRT constraints. Thus, the line moves down if that makes the constraints stricter but does not move down if that would expand the redundant area. In particular, the top line must not be move down, but clearly Intel moved the line down and generated the faulty lookup table. Intel, however, has a different explanation for the bug. The Intel white paper states that the problem was in a script that downloaded the table into a PLA: an error caused the script to omit a few entries from the PLA.27 I don't believe this explanation: the missing terms match a mathematical error, not a copying error. I suspect that Intel's statement is technically true but misleading: they ran a C program (which they called a script) to generate the table but the program had a mathematical error in the bounds. In his book "The Pentium Chronicles", Robert Colwell, architect of the Pentium Pro, provides a different explanation of the FDIV bug. Colwell claims that the Pentium design originally used the same lookup table as the 486, but shortly before release, the engineers were pressured by management to shrink the circuitry to save die space. The engineers optimized the table to make it smaller and had a proof that the optimization would work. Unfortunately, the proof was faulty, but the testers trusted the engineers and didn't test the modification thoroughly, causing the Pentium to be released with the bug. The problem with this explanation is that the Pentium was designed from the start with a completely different division algorithm from the 486: the Pentium uses radix-4 SRT, while the 486 uses standard binary division. Since the 486 doesn't have a lookup table, the story falls apart. Moreover, the PLA could trivially have been made smaller by removing the 8 unused rows, so the engineers clearly weren't trying to shrink it. My suspicion is that since Colwell developed the Pentium Pro in Oregon but the original Pentium was developed in California, Colwell didn't get firsthand information on the Pentium problems. How Intel fixed the bug Intel's fix for the bug was straightforward but also surprising. You'd expect that Intel added the five missing table values to the PLA, and this is what was reported at the time. The New York Times wrote that Intel fixed the flaw by adding several dozen transistors to the chip. EE Times wrote that "The fix entailed adding terms, or additional gate-sequences, to the PLA." However, the updated PLA (below) shows something entirely different. The updated PLA is exactly the same size as the original PLA. However, about 1/3 of the terms were removed from the PLA, eliminating hundreds of transistors. Only 74 of the PLA's 120 rows are used, and the rest are left empty. (The original PLA had 8 empty rows.) How could removing terms from the PLA fix the problem? The updated PLA has 46 unused rows. The explanation is that Intel didn't just fill in the five missing table entries with the correct value of 2. Instead, Intel filled all the unused table entries with 2, as shown below. This has two effects. First, it eliminates any possibility of hitting a mistakenly-empty entry. Second, it makes the PLA equations much simpler. You might think that more entries in the table would make the PLA larger, but the number of PLA terms depends on the structure of the data. By filling the unused cells with 2, the jagged borders between the unused regions (white) and the "2" regions (yellow) disappear. As explained earlier, a large rectangle can be covered by a single PLA term, but a jagged border requires a lot of terms. Thus, the updated PLA is about 1/3 smaller than the original, flawed PLA. One consequence is that the terms in the new PLA are completely different from the terms in the old PLA so one can't point to the specific transistors that fixed the bug. Comparison of the faulty lookup table (left) and the corrected lookup table (right). The image below shows the first 14 rows of the faulty PLA and the first 14 rows of the fixed PLA. As you can see, the transistor pattern (and thus the PLA terms) are entirely different. The doped silicon is darkened in the second image due to differences in how I processed the dies to remove the metal layers. Top of the faulty PLA (left) and the fixed PLA (right). The metal layers were removed to show the silicon of the transistors. (Click for a larger image.) Impact of the FDIV bug How important is the Pentium bug? This became a highly controversial topic. A failure of a random division operation is very rare: about one in 9 billion values will trigger the bug. Moreover, an erroneous division is still mostly accurate: the error is usually in the 9th or 10th decimal digit, with rare worst-case error in the 4th significant digit. Intel's whitepaper claimed that a typical user would encounter a problem once every 27,000 years, insignificant compared to other sources of error such as DRAM bit flips. Intel said: "Our overall conclusion is that the flaw in the floating point unit of the Pentium processor is of no concern to the vast majority of users. A few users of applications in the scientific/engineering and financial engineering fields may need to employ either an updated processor without the flaw or a software workaround." However, IBM performed their own analysis,29 suggesting that the problem could hit customers every few days, and IBM suspended Pentium sales. (Coincidentally, IBM had a competing processor, the PowerPC.) The battle made it to major newspapers; the Los Angeles Times split the difference with Study Finds Both IBM, Intel Off on Error Rate. Intel soon gave in and agreed to replace all the Pentiums, making the issue moot. I mostly agree with Intel's analysis. It appears that only one person (Professor Nicely) noticed the bug in actual use.28 The IBM analysis seems contrived to hit numbers that trigger the error. Most people would never hit the bug and even if they hit it, a small degradation in floating-point accuracy is unlikely to matter to most people. Looking at society as a whole, replacing the Pentiums was a huge expense for minimal gain. On the other hand, it's reasonable for customers to expect an accurate processor. Note that the Pentium bug is deterministic: if you use a specific divisor and dividend that trigger the problem, you will get the wrong answer 100% of the time. Pentium engineer Ken Shoemaker suggested that the outcry over the bug was because it was so easy for customers to reproduce. It was hard for Intel to argue that customers would never encounter the bug when customers could trivially see the bug on their own computer, even if the situation was artificial. Conclusions The FDIV bug is one of the most famous processor bugs. By examining the die, it is possible to see exactly where it is on the chip. But Intel has had other important bugs. Some early 386 processors had a 32-bit multiply problem. Unlike the deterministic FDIV bug, the 386 would unpredictably produce the wrong results under particular temperature/voltage/frequency conditions. The underlying issue was a layout problem that didn't provide enough elctrical margin to handle the worst-case situation. Intel sold the faulty chips but restricted them to the 16-bit market; bad chips were labeled "16 BIT S/W ONLY", while the good processors were marked with a double sigma. Although Intel had to suffer through embarrassing headlines such as Some 386 Systems Won't Run 32-Bit Software, Intel Says, the bug was soon forgotten. Bad and good versions of the 386. Note the labels on the bottom line. Photos (L), (R) by Thomas Nguyen, (CC BY-SA 4.0) Another memorable Pentium issue was the "F00F bug", a problem where a particular instruction sequence starting with F0 0F would cause the processor to lock up until rebooted.30 The bug was found in 1997 and solved with an operating system update. The bug is presumably in the Pentium's voluminous microcode. The microcode is too complex for me to analyze, so don't expect a detailed blog post on this subject. :-) You might wonder why Intel needed to release a new revision of the Pentium to fix the FDIV bug, rather than just updating the microcode. The problem was that microcode for the Pentium (and earlier processors) was hard-coded into a ROM and couldn't be modified. Intel added patchable microcode to the Pentium Pro (1995), allowing limited modifications to the microcode. Intel originally implemented this feature for chip debugging and testing. But after the FDIV bug, Intel realized that patchable microcode was valuable for bug fixes too.31 The Pentium Pro stores microcode in ROM, but it also has a static RAM that holds up to 60 microinstructions. During boot, the BIOS can load a microcode patch into this RAM. In modern Intel processors, microcode patches have been used for problems ranging from the Spectre vulnerability to voltage problems. The Pentium PLA with the top metal layer removed, revealing the M2 and M1 layers. The OR and AND planes are at the top and bottom, with drivers and control logic in the middle. As the number of transistors in a processor increased exponentially, as described by Moore's Law, processors used more complex circuits and algorithms. Division is one example. Early microprocessors such as the Intel 8080 (1974, 6000 transistors) had no hardware support for division or floating point arithmetic. The Intel 8086 (1978, 29,000 transistors) implemented integer division in microcode but required the 8087 coprocessor chip for floating point. The Intel 486 (1989, 1.2 million transistors) added floating-point support on the chip. The Pentium (1993, 3.1 million transistors) moved to the faster but more complicated SRT division algorithm. The Pentium's division PLA alone has roughly 4900 transistor sites, more than a MOS Technology 6502 processor—one component of the Pentium's division circuitry uses more transistors than an entire 1975 processor. The long-term effect of the FDIV bug on Intel is a subject of debate. On the one hand, competitors such as AMD benefitted from Intel's error. AMD's ads poked fun at the Pentium's problems by listing features of AMD's chips such as "You don't have to double check your math" and "Can actually handle the rigors of complex calculations like division." On the other hand, Robert Colwell, architect of the Pentium Pro, said that the FDIV bug may have been a net benefit to Intel as it created enormous name recognition for the Pentium, along with a demonstration that Intel was willing to back up its brand name. Industry writers agreed; see The Upside of the Pentium Bug. In any case, Intel survived the FDIV bug; time will tell how Intel survives its current problems. I plan to write more about the implementation of the Pentium's PLA, the adder, and the test circuitry. Until then, you may enjoy reading about the Pentium Navajo rug. (The rug represents the P54C variant of the Pentium, so it is safe from the FDIV bug.) Thanks to Bob Colwell and Ken Shoemaker for helpful discussions. Footnotes and references The book Inside Intel says that Vin Dham, the "Pentium czar", found the FDIV problem in May 1994. The book "The Pentium Chronicles" says that Patrice Roussel, the floating-point architect for Intel's upcoming Pentium Pro processor, found the FDIV problem in Summer 1994. I suspect that the bug was kept quiet inside Intel and was discovered more than once. ↩ The divisor being a prime number has nothing to do with the bug. It's just a coincidence that the problem was found during research with prime numbers. ↩ See Nicely's FDIV page for more information on the bug and its history. Other sources are the books Creating the Digital Future, The Pentium Chronicles, and Inside Intel. The New York Times wrote about the bug: Flaw Undermines Accuracy of Pentium Chips. Computerworld wrote Intel Policy Incites User Threats on threats of a class-action lawsuit. IBM's response is described in IBM Deals Blow to a Rival as it Suspends Pentium Sales ↩ Talk show host David Letterman joked about the Pentium on December 15: "You know what goes great with those defective Pentium chips? Defective Pentium salsa!" Although a list of Letterman-style top ten Pentium slogans circulated, the list was a Usenet creation. There's a claim that Jay Leno also joked about the Pentium, but I haven't found verification. ↩ Processors have many more bugs than you might expect. Intel's 1995 errata list for the Pentium had "21 errata (including the FDIV problem), 4 changes, 16 clarifications, and 2 documentation changes." See Pentium Processor Specification Update and Intel Releases Pentium Errata List. ↩ Intel published full-page newspaper ads apologizing for its handling of the problem, stating: "What Intel continues to believe is an extremely minor technical problem has taken on a life of its own." Intel's apology letter, published in Financial Times. Note the UK country code in the phone number.  ↩ Tim Coe's reverse engineering of the Pentium divider was described on the Usenet group comp.sys.intel, archived here. To summarize, Andreas Kaiser found 23 failing reciprocals. Tim Coe determined that most of these failing reciprocals were of the form 3*(2^(K+30)) - 1149*(2^(K-(2*J))) - delta*(2^(K-(2*J))). He recognized that the factor of 2 indicated a radix-4 divider. The extremely low probability of error indicated the presence of a carry save adder; the odds of both the sum and carry bits getting long patterns of ones were very low. Coe constructed a simulation of the divider that matched the Pentium's behavior and noted which table entries must be faulty. ↩ The main papers on the FDIV bug are Computational Aspects of the Pentium Affair, It Takes Six Ones to Reach a Flaw, The Mathematics of the Pentium Division Bug, The Truth Behind the Pentium Bug, Anatomy of the Pentium Bug, and Risk Analysis of the Pentium Bug. Intel's whitepaper is Statistical Analysis of Floating Point Flaw in the Pentium Processor; I archived IBM's study here. ↩ The Pentium uses floating point numbers that follow the IEEE 754 standard. Internally, floating point numbers are represented with 80 bits: 1 bit for the sign, 15 bits for the exponent, and 64 bits for the significand. Externally, floating point numbers are 32-bit single-precision numbers or 64-bit double-precision numbers. Note that the number of significand bits limits the accuracy of a floating-point number. ↩ The SRT division algorithm is named after the three people who independently created it in 1957-1958: Sweeney at IBM, Robertson at the University of Illinois, and Tocher at Imperial College London. The SRT algorithm was developed further by Atkins in his PhD research (1970). The SRT algorithm became more practical in the 1980s as chips became denser. Taylor implemented the SRT algorithm on a board with 150 chips in 1981. The IEEE floating point standard (1985) led to a market for faster floating point circuitry. For instance, the Weitek 4167 floating-point coprocessor chip (1989) was designed for use with the Intel 486 CPU (datasheet) and described in an influential paper. Another important SRT implementation is the MIPS R3010 (1988), the coprocessor for the R3000 RISC processor. The MIPS R3010 uses radix-4 SRT for division with 9 bits from the partial remainder and 9 bits from the divisor, making for a larger lookup table and adder than the Pentium (link). To summarize, when Intel wanted to make division faster on the Pentium (1993), the SRT algorithm was a reasonable choice. Competitors had already implemented SRT and multiple papers explained how SRT worked. The implementation should have been straightforward and bug-free. ↩ The dimensions of the lookup table can't be selected arbitrarily. In particular, if the table is too small, a cell may need to hold two different q values, which isn't possible. Note that constructing the table is only possible due to the redundancy of SRT. For instance, if some values in the call require q=1 and other values require q=1 or 2, then the value q=1 can be assigned to the cell. ↩ In the white paper, Intel calls the PLA a Programmable Lookup Array, but that's an error; it's a Programmable Logic Array. ↩ I'll explain a PLA in a bit more detail in this footnote. An example of a sum-of-products formula with inputs a and b is ab' + a'b + ab. This formula has three sum terms, so it requires three rows in the PLA. However, this formula can be reduced to a + b, which uses a smaller two-row PLA. Note that any formula can be trivially expressed with a separate product term for each 1 output in the truth table. The hard part is optimizing the PLA to use fewer terms. ↩ A ROM and a PLA have many similarities. You can implement a ROM with a PLA by using the AND terms to decode addresses and the OR terms to hold the data. Alternatively, you can replace a PLA with a ROM by putting the function's truth table into the ROM. ROMs are better if you want to hold arbitrary data that doesn't have much structure (such as the microcode ROMs). PLAs are better if the functions have a lot of underlying structure. The key theoretical difference between a ROM and a PLA is that a ROM activates exactly one row at a time, corresponding to the address, while a PLA may activate one row, no rows, or multiple rows at a time. Another alternative for representing functions is to use logic gates directly (known as random logic); moving from the 286 to the 386, Intel replaced many small PLAs with logic gates, enabled by improvements in the standard-cell software. Intel's design process is described in Coping with the Complexity of Microprocessor Design. ↩ In 1982, Intel developed a program called LOGMIN to automate PLA design. The original LOGMIN used an exhaustive exponential search, limiting its usability. See A Logic Minimizer for VLSI PLA Design. For the 386, Intel used Espresso, a heuristic PLA minimizer that originated at IBM and was developed at UC Berkeley. Intel probably used Espresso for the Pentium, but I can't confirm that. ↩ The Pentium's PLA is split into a top half and a bottom half, so you might expect the top half would generate a quotient of 1 and the bottom half would generate a quotient of 2. However, the rows for the two quotients are shuffled together with no apparent pattern. I suspect that the PLA minimization software generated the order arbitrarily. ↩ Conceptually, the PLA consists of AND gates feeding into OR gates. To simplify the implementation, both layers of gates are actually NOR gates. Specifically, if any transistor in a row turns on, the row will be pulled to ground, producing a zero. De Morgan's laws show that the two approaches are the same, if you invert the inputs and outputs. I'm ignoring this inversion in the diagrams. Note that each square can form a transistor on the left, the right, or both. The image must be examined closely to distinguish these cases. Specifically, if the polysilicon line produces a transistor, horizontal lines are visible in the polysilicon. If there are no horizontal lines, the polysilicon passes by without creating a transistor. ↩ Each OR plane has four outputs, so there are eight outputs in total. These outputs are combined with logic gates to generate the desired two outputs (quotient of 1 or 2). I'm not sure why the PLA is implemented in this fashion. Each row alternates between an output on the left and an output on the right, but I don't think this makes the layout any denser. As far as I can tell, the extra outputs just waste space. One could imagine combining the outputs in a clever way to reduce the number of terms, but instead the outputs are simply OR'd together. ↩ The dynamics of the division algorithm are interesting. The computation of a particular division will result in the partial remainder bouncing from table cell to table cell, while remaining in one column of the table. I expect this could be analyzed in terms of chaotic dynamics. Specifically, the partial remainder interval is squished down by the subtraction and then expanded when multiplied by 4. This causes low-order bits to percolate upward so the result is exponentially sensitive to initial conditions. I think that the division behavior satisfies the definition of chaos in Dynamics of Simple Maps, but I haven't investigated this in detail. You can see this chaotic behavior with a base-10 division, e.g. compare 1/3.0001 to 1/3.0002: 1/3.0001=0.33332222259258022387874199947368393726705454969006... 1/3.0002=0.33331111259249383619151572689224512820860216424246... I tried to make a fractal out of the SRT algorithm and came up with the image below. There are 5 bands for convergence, each made up of 5 sub-bands, each made up of 5 sub-sub bands, and so on, corresponding to the 5 q values. A fractal showing convergence or divergence of SRT division as the scale factor (X-axis) ranges from the normal value of 4 to infinity. The Y-axis is the starting partial remainder. The divisor is (arbitrarily) 1.5. Red indicates convergence; gray is darker as the value diverges faster.  ↩ The algebra behind the bound of 8/3 is that p (the partial remainder) needs to be in an interval that stays the same size each step. Each step of division computes pnew = (pold - q*d)*4. Thus, at the boundary, with q=2, you have p = (p-2*d)*4, so 3p=8d and thus p/d = 8/3. Similarly, the other boundary, with q=-2, gives you p/d = -8/3. ↩ I'm not completely happy with the 8-bit carry-lookahead adder. Coe's mathematical analysis in 1994 showed that the carry-lookahead adder operates on 7 bits. The adder in the Pentium has two 8-bit inputs connected to another part of the division circuit. However, the adder's bottom output bit is not connected to anything. That would suggest that the adder is adding 8 bits and then truncating to 7 bits, which would reduce the truncation error compared to a 7-bit adder. However, when I simulate the division algorithm this way, the FDIV bug doesn't occur. Wiring the bottom input bits to 0 would explain the behavior, but that seems pointless. I haven't examined the circuitry that feeds the adder, so I don't have a conclusive answer. ↩ Half of the circuitry in the adder block is used to test the lookup table. The reason is that a chip such as the Pentium is very difficult to test: if one out of 3.1 million transistors goes bad, how do you detect it? For a simple processor like the 8080, you can run through the instruction set and be fairly confident that any problem would turn up. But with a complex chip, it is almost impossible to come up with an instruction sequence that would test every bit of the microcode ROM, every bit of the cache, and so forth. Starting with the 386, Intel added circuitry to the processor solely to make testing easier; about 2.7% of the transistors in the 386 were for testing. To test a ROM inside the processor, Intel added circuitry to scan the entire ROM and checksum its contents. Specifically, a pseudo-random number generator runs through each address, while another circuit computes a checksum of the ROM output, forming a "signature" word. At the end, if the signature word has the right value, the ROM is almost certainly correct. But if there is even a single bit error, the checksum will be wrong and the chip will be rejected. The pseudo-random numbers and the checksum are both implemented with linear feedback shift registers (LFSR), a shift register along with a few XOR gates to feed the output back to the input. For more information on testing circuitry in the 386, see Design and Test of the 80386, written by Pat Gelsinger, who became Intel's CEO years later. Even with the test circuitry, 48% of the transistor sites in the 386 were untested. The instruction-level test suite to test the remaining circuitry took almost 800,000 clock cycles to run. The overhead of the test circuitry was about 10% more transistors in the blocks that were tested. In the Pentium, the circuitry to test the lookup table PLA is just below the 7-bit adder. An 11-bit LFSR creates the 11-bit input value to the lookup table. A 13-bit LFSR hashes the two-bit quotient result from the PLA, forming a 13-bit checksum. The checksum is fed serially to test circuitry elsewhere in the chip, where it is merged with other test data and written to a register. If the register is 0 at the end, all the tests pass. In particular, if the checksum is correct, you can be 99.99% sure that the lookup table is operating as expected. The ironic thing is that this test circuit was useless for the FDIV bug: it ensured that the lookup table held the intended values, but the intended values were wrong. Why did Intel generate test addresses with a pseudo-random sequence instead of a sequential counter? It turns out that a linear feedback shift register (LFSR) is slightly more compact than a counter. This LFSR trick was also used in a touch-tone chip and the program counter of the Texas Instruments TMS 1000 microcontroller (1974). In the TMS 1000, the program counter steps through the program pseudo-randomly rather than sequentially. The program is shuffled appropriately in the ROM to counteract the sequence, so the program executes as expected and a few transistors are saved. ↩ One unusual feature of the Pentium is that it uses BiCMOS technology: both bipolar and CMOS transistors. Note the distinctive square boxes in the driver circuitry; these are bipolar transistors, part of the high-speed drivers. Three bipolar transistors. These transistors transmit the quotient to the rest of the division circuitry.  ↩ I think the partial remainder is actually 67 bits because there are three extra bits to handle rounding. Different parts of the floating-point datapath have different widths, depending on what width is needed at that point. ↩ In this long footnote, I'll attempt to explain why the FDIV bug is so rare, using heatmaps. My analysis of Intel's lookup table shows several curious factors that almost cancel out, making failures rare but not impossible. (For a rigorous explanation, see It Takes Six Ones to Reach a Flaw and The Mathematics of the Pentium Division Bug. These papers explain that, among other factors, a bad divisor must have six consecutive ones in positions 5 through 10 and the division process must go through nine specific steps, making a bad result extremely uncommon.) The diagram below shows a heatmap of how often each table cell is accessed when simulating a generic SRT algorithm with a carry-save adder. The black lines show the boundaries of the quotient regions in the Pentium's lookup table. The key point is that the top colored cell in each column is above the black line, so some table cells are accessed but are not defined in the Pentium. This shows that the Pentium is missing 16 entries, not just the 5 entries that are usually discussed. (For this simulation, I generated the quotient digit directly from the SRT bounds, rather than the lookup table, selecting the digit randomly in the redundant regions.) A heatmap showing the table cells accessed by an SRT simulation. The diagram is colored with a logarithmic color scale. The blue cells are accessed approximately uniformly. The green cells at the boundaries are accessed about 2 orders of magnitude less often. The yellow-green cells are accessed about 3 orders of magnitude less often. The point is that it is hard to get to the edge cells since you need to start in the right spot and get the right quotient digit, but it's not extraordinarily hard. (The diagram also shows an interesting but ultimately unimportant feature of the Pentium table: at the bottom of the diagram, five white cells are above the back line. This shows that the Pentium assigns values to five table cells that can't be accessed. (This was also mentioned in "The Mathematics of the Pentium Bug".) These cells are in the same columns as the 5 missing cells, so it would be interesting if they were related to the missing cells. But as far as I can tell, the extra cells are due to using a bound of "greater or equals" rather than "greater", unrelated to the missing cells. In any case, the extra cells are harmless.) The puzzling factor is that if the Pentium table has 16 missing table cells, and the SRT uses these cells fairly often, you'd expect maybe 1 division out of 1000 or so to be wrong. So why are division errors extremely rare? It turns out that the structure of the Pentium lookup table makes some table cells inaccessible. Specifically, the table is arbitrarily biased to pick the higher quotient digit rather than the lower quotient digit in the redundant regions. This has the effect of subtracting more from the partial remainder, pulling the partial remainder away from the table edges. The diagram below shows a simulation using the Pentium's lookup table and no carry-save adder. Notice that many cells inside the black lines are white, indicating that they are never accessed. This is by coincidence, due to arbitrary decisions when constructing in the lookup table. Importantly, the missing cells just above the black line are never accessed, so the missing cells shouldn't cause a bug. A heatmap showing the table cells accessed by an SRT simulation using the Pentium's lookup table but no carry-save adder. Thus, Intel almost got away with the missing table entries. Unfortunately, the carry-save adder makes it possible to reach some of the otherwise inaccessible cells. Because the output from the carry-save adder is truncated, the algorithm can access the table cell below the "right" cell. In the redundant regions, this can yield a different (but still valid) quotient digit, causing the next partial remainder to end up in a different cell than usual. The heatmap below shows the results. A heatmap showing the probability of ending up in each table cell when using the Pentium's division algorithm. In particular, five cells above the black line can be reached: these are instances of the FDIV bug. These cells are orange, indicating that they are about 9 orders of magnitude less likely than the rest of the cells. It's almost impossible to reach these cells, requiring multiple "unlucky" values in a row from the carry-save adder. To summarize, the Pentium lookup table has 16 missing cells. Purely by coincidence, the choices in the lookup table make many cells inaccessible, which almost counteracts the problem. However, the carry-save adder provides a one-in-a-billion path to five of the missing cells, triggering the FDIV bug. One irony is that if division errors were more frequent, Intel would have caught the FDIV bug before shipping. But if division errors were substantially less frequent, no customers would have noticed the bug. Inconveniently, the frequency of errors fell into the intermediate zone: errors were too rare for Intel to spot them, but frequent enough for a single user to spot them. (This makes me wonder what other astronomically infrequent errors may be lurking in processors.) ↩ Anatomy of the Pentium Bug reached a similar conclusion, stating "The [Intel] White Paper attributes the error to a script that incorrectly copied values; one is nevertheless tempted to wonder whether the rule for lowering thresholds was applied to the 8D/3 boundary, which would be an incorrect application because that boundary is serving to bound a threshold from below." (That paper also hypothesizes that the table was compressed to 6 columns, a hypothesis that my examination of the die disproves.) ↩ The Intel white paper describes the underlying cause of the bug: "After the quantized P-D plot (lookup table) was numerically generated as in Figure 4-1, a script was written to download the entries into a hardware PLA (Programmable Lookup Array). An error was made in this script that resulted in a few lookup entries (belonging to the positive plane of the P-D plot) being omitted from the PLA." The script explanation is repeated in The Truth Behind the Pentium Bug: "An engineer prepared the lookup table on a computer and wrote a script in C to download it into a PLA (programmable logic array) for inclusion in the Pentium's FPU. Unfortunately, due to an error in the script, five of the 1066 table entries were not downloaded. To compound this mistake, nobody checked the PLA to verify the table was copied correctly." My analysis suggests that the table was copied correctly; the problem was that the table was mathematically wrong. ↩ It's not hard to find claims of people encountering the Pentium division bug, but these seem to be in the "urban legend" category. Either the problem is described second-hand, or the problem is unrelated to division, or the problem happened much too frequently to be the FDIV bug. It has been said that the game Quake would occasionally show the wrong part of a level due to the FDIV bug, but I find that implausible. The "Intel Inside—Don't Divide" Chipwreck describes how the division bug was blamed for everything from database and application server crashes to gibberish text. ↩ IBM's analysis of the error rate seems contrived, coming up with reasons to use numbers that are likely to cause errors. In particular, IBM focuses on slightly truncated numbers, either numbers with two decimal digits or hardcoded constants. Note that a slightly truncated number is much more likely to hit a problem because its binary representation will have multiple 1's in a row, a necessity to trigger the bug. Another paper Risk Analysis of the Pentium Bug claims a risk of one in every 200 divisions. It depends on "bruised integers", such as 4.999999, which are similarly contrived. I'll also point out that if you start with numbers that are "bruised" or otherwise corrupted, you obviously don't care about floating-point accuracy and shouldn't complain if the Pentium adds slightly more inaccuracy. The book "Inside Intel" says that "the IBM analysis was quite wrong" and "IBM's intervention in the Pentium affair was not an example of the company on its finest behavior" (page 364). ↩ The F00F bug happens when an invalid compare-and-exchange instruction leaves the bus locked. The instruction is supposed to exchange with a memory location, but the invalid instruction specifies a register instead causing unexpected behavior. This is very similar to some undocumented instructions in the 8086 processor where a register is specified when memory is required; see my article Undocumented 8086 instructions, explained by the microcode. ↩ For details on the Pentium Pro's patchable microcode, see P6 Microcode Can Be Patched. But patchable microcode dates back much earlier. The IBM System/360 mainframes (1964) had microcode that could be updated in the field, either to fix bugs or to implement new features. These systems stored microcode on metalized Mylar sheets that could be replaced as necessary. In that era, semiconductor ROMs didn't exist, so Mylar sheets were also a cost-effective way to implement read-only storage. See TROS: How IBM mainframes stored microcode in transformers. ↩