Summary of “Divide and Conquer”
Why was Thomas Nicely so
obsessed with finding twin primes? It was the early 90’s and public
access to computers with powerful calculation capabilities was finally
becoming a reality. Nicely, a professor of mathematics at Lynchburg
College, was weighing the feasibility of several different “unfinished”
mathematical queries. He was looking for a problem much too difficult to
solve with pen and paper or even the most powerful calculator—yet would
not depend on a difficult to access supercomputer either. With
innovations in desktop computing, such as Intel’s Pentium chip, Nicely
set out to elaborate on a mathematical problem by harnessing, as well as
challenging, the computer processing capabilities of the era. His
research was “to serve as a model for other people working in small
college environments.” Of the many mathematical theories that needed
further exploration, the question of whether the occurrence of twin
primes continued infinitely as you counted up and at what exact number
did the sum of the reciprocals of the twin primes converge (known as
Brun’s sum) was the tantalizing question Nicely wanted to answer. In
1993, Nicely decided to solve Brun’s sum to such a precision that would
have been impossible even half a decade before.
Twin primes are
consecutive pairs of odd primes: 3 and 5, 5 and 7, or 11 and 13 are the
first few of an infinite set of examples. Brun’s sum was an estimation
of the occurrence of twin primes. But, because humans are only capable
of counting and keeping track of a finite set of numbers and the
occurrence of twin primes can be sporadic, Brun’s sum was not as precise
as it could be. Why is this important, you may ask? Well, let’s start
this mathematical conundrum at the beginning—300 BC. The “father of
Geometry”, Euclid of Alexandria, proves that there are,
in fact,
an infinite number of primes! Fast forward two millennia to Europe in
1896 --Charles-Jean Étienne Gustave Nicolas de la Vallée Poussin of
Belgium and Jacques Hadamard of France independently proved the Prime
Number Theorem. This theorem describes how prime numbers are distributed
among the positive integers. It posits that primes become less common
the higher you count. The Prime Number Theorem answered many of the
unsolved mysteries of prime numbers…but the solution to the enigma of
twin primes remained out of the grasp for mathematicians of the era. I
n
Norway, 1919, twenty years later, Viggo Brun postulated an upper bound
for twin primes; yet no lower bounds were found to prove twin primes
occurred in an infinite sequence. Brun also developed the titular
Brun’s sum. The Brun sum states that if you reciprocate all the twin
primes and add them together – the sum is finite. Furthermore, the
infinite series converges to some number “B.” In 1974, Shanks and Wrench
Jr. -- naval mathematicians working in Bethesda, Maryland, tested
Brun’s sum by investigating all the twin primes in the set of the first
two million prime numbers. A year later, Australian mathematician
Richard Brent tracked down all the twin primes of the first one-hundred
billion prime numbers! Brent found an astonishing 224,376,048 twin
primes and obtained a numerical estimate of the convergence of Brun’s
sum: 1.90216054. As amazing as that was, Nicely knew he could take the
next leap in calculating an even more precise Brun’s sum—he was going to
calculated the set of prime numbers up into the trillions!
However,
Nicely’s quest was not without difficulties. Because of the fallibility
of new technology and the dilution of accountability of software
development within massive corporations, imperfect products were
sometimes released. Enter Intel. Intel released a faster and more
powerful Pentium chip in 1993. In less than 2 years, nearly one million
Pentiums had been sold at a retail price of $1,000 each. About 18
months after its release, a previously unknown flaw in the processor’s
floating point unit was finally discovered by the company.
However,
Intel swept this discovery under the rug. They figured no user would be
using the processor for the kind of high-stakes, ultra-precise
computation that would generate a meaningful error. They also did not
want to give out replacements and refunds for the near million units
that were already out on the market!
When Thomas Nicely
discovered that Intel had not issued a recall, he decided: No more Mr.
Nicely. Nicely confronted Intel directly- when he was ignored he took
his shocking discovery to the Internet. Word of mouth spread and public
opinion of Intel fell. The consumers demanded their money back. Intel
tried to argue that the error only interfered in a small minority of
very specific problems. Yet, the consumers insisted and Intel caved to
public demand. They issued a refund of the faulty Pentium chip at the
consumer’s request—and fortunately, the blow to Intel’s reputation was
short lived. In fact, it seemed to have the opposite effect. The chip
was a hot seller that Christmas and by mid-1995—tens of millions units
had been sold.
Discussion
The article “Divide and
Conquer” is an important read for Computer Science students because it
is both a history piece capturing the growing pains of an industry in
the early 90’s as well as a cautionary tale alerting the public to the
surprising fallibility of computers. The quote: “In a sense, all
computers do division wrong,” is a shocking realization. I, myself, am
so awed by the beyond human processing capabilities of computers that I
inherently bestow upon them supernatural powers. But then to see that
long division is a relatively complex process for
computers and that they can only process a finite amount of decimal points—it brings the truth of computers out to light.
The
descriptions of how Nicely went about solving Brun’s sum, despite
setbacks, could be very eye opening for computer science students. The
amount of trouble Nicely went through to ensure that safeguards were in
effect and no unexpected error from the hardware would result in a large
loss of data was very smart. Carpenters have a saying, “Measure twice,
cut once.” Meaning, that if you do more pre-planning work than you even
think is necessary, it can really save you time and headache further
down the road.
The safeguards Nicely enacted paid off in spades.
For example, he would have two different computers with different
processing equipment (either a ‘486’ or a Pentium chip) compute the same
set of data—any discrepancies between the two was a red flag that
either one, the other, or BOTH computers were making processing errors!
Another example, Nicely would store the results outputted by each
computer at the end of each billion numbers. That way, if two different
machines settled on a different end value, Nicely could look back
through the data to find the range where the two number sets started to
differ. Another security measure Nicely took to ensure accuracy, is he
would check his output against previously published result. Furthermore,
Nicely decided to compute Brun’s sum using two different methods. One
was to use the computer’s floating point unit to calculate each
reciprocal to nineteen digits and the other was a ultra-precision
algorithm that measured up to twenty-six (and later fifty-three) digits
accuracy! Also, like any good scientist, Nicely had a healthy
skepticism…he did not just take it for granted that machines will behave
the way you want
them too. And that scientific-method mentality
can be an inspiration for anyone breaking new ground for any perplexing
un-solved problem.
References
Cipra, B. (1995). Divide and Conquer. What’s Happening in Mathematical Sciences
Volume 3.
No comments:
Post a Comment