170
Letters to the Editor
A
ugust
2013
N
otices
of
the
AMs
841
important critique of contemporary
mathematics education in America.
In his review in the April 2013 No-
tices, William Schmidt calls Lockhart’s
book “realistic”, saying, “I share in
much of the author’s lament” and
proclaiming “the author provides an
accurate characterization of math-
ematics instruction in the United
States.” Having accepted Lockhart’s
diagnosis—the dominant paradigm
driving our system of mathematics
education is irrevocably broken—the
balance of Schmidt’s review is, unfor-
tunately, an exercise in avoidance.
To call Lockhart’s “Mathemati-
cal Reality” too “abstract” and “un-
realistic” is disingenuous. Schmidt
repeatedly uses psychological pro-
jection, defensively ascribing the
shortcomings of our current system
onto Lockhart’s vision for something
new. Diversions such as these keep us
from breaking out of the confines of
an admittedly broken paradigm. As
many examples in the history of sci-
ence illustrate, if we continue blithely
down this dysfunctional road, as
Schmidt would seem to have us do,
then we are Alice and have gone down
the rabbit-hole, not Lockhart.
Lockhart is not simply an ideal-
ist who has thrown his hands up.
Throughout his lament he carefully
identifies some of the important as-
sumptions that underlie the current
paradigm which we should reject, and
he identifies assumptions—which he
collects under the moniker “Math-
ematical Reality”—that could serve
as part of the foundation for a more
successful paradigm.
Schmidt expects too much of one
thoughtful messenger. It is the re-
sponsibility of our entire community
to honestly respond to these chal-
lenges, to determine how educational
practice may provide alternatives,
and to help understand what new
approaches could look like on a “day-
to-day instructional level.”
Existing programs developed
under assumptions similar to Lock-
hart’s “Mathematical Reality” can in-
form our efforts. One such initiative
is the National Science Foundation-
supported project Discovering the
Art of Mathematics. Its inquiry-based
approach requires students to “actu-
ally do some mathematics, and come
The Rudins in Hawaii
On behalf of the math faculty here at
the University of Hawaii, I would like
to express our sadness at the passing
first of Walter Rudin and now too of
Mary Ellen Rudin. The math depart-
ment was quite fortunate to have the
Rudins as very special and regular
visitors to our department over more
than twenty years. It all started with
their sabbatical visit in the spring
of 1982 and continued afterwards
with biennial month-long stays typi-
cally during the months of January
or February when the weather in
Madison was particularly cold. Their
retirements from the University of
Wisconsin math department gave
them the flexibility to escape those
cold winters and enjoy our tropical
weather and beautiful beaches. They
spent most of their visits staying
in beach cottages on Kailua Beach,
which is located on the windward
side of the island of Oahu. Their fa-
vorite activity was simply sitting on
their beach chairs and enjoying the
sunshine.
The Rudins became part of our
departmental “family”. Every visit
included colloquiums from each of
them along with “math talk” with
faculty members: Walter mostly with
the analysis group and Mary Ellen
mostly with the logic, topology, and
universal algebra groups. Of course
there was always plenty of social
interaction too. Every visit included
a “banquet” at the New Chinese
Restaurant in Kailua, when the math
department would basically take over
the small restaurant with a large
crowd. This was not a fancy place,
but it was Walter’s and Mary Ellen’s
favorite spot to eat in Kailua.
Walter and Mary Ellen also made
some extra trips so that their two
daughters, Catherine and Eleanor,
and their son, Charlie, would have
a place to stay during their visits to
Hawaii. Some of our faculty members
provided windsurfing lessons for
Charlie and his friends.
Their last visit to Hawaii was in
2005. By that time Walter’s health
problems had reached a point that
travel was quite difficult for him.
Mary Ellen on the other hand seemed
like she would live forever at that
time, but sadly all things must end.
The passing of the Rudins marks the
end of an era for us here in Hawaii as
I’m sure it does also for many others
around the world.
—L. Thomas Ramsey, chair,
University of Hawaii
Math Department
ramsey@math.hawaii.edu
(Received April 15, 2013)
Correction to Conway Interview
I thoroughly enjoyed the “Interview
with John Horton Conway” in the
May Notices (vol. 60, no. 5, p. 567).
Conway’s deep mathematical insights
over a long lifetime are most impres-
sive. But on page 573 Conway ap-
pears to mix up two famous integer
sequences, namely the Hofstadter-
Conway $10000 sequence and the
Hofstadter Q-sequence. These are,
respectively, numbers A004001 and
A005185 in the On-Line Encyclopedia
of Integer Sequences. Conway’s anec-
dote concerns the former sequence,
but the formula corresponds to the
latter. The recursion given is f(0)=0,
f(1)=1, f(n)=f(n–f(n–1)) + f(n–f(n–2)),
where the initial values are also mis-
taken. Ironically this adds further
terms to the sequence of mistakes
recounted in the interview.
—Michael Josephy
Universidad de Costa Rica
MICHAEL.JOSEPHY@ucr.ac.cr
(Received May 10, 2013)
Realizing Mathematical Reality
In A Mathematician’s Lament, Paul
Lockhart has written a provocative and
Photo courtesy of the University of Hawaii
Mathematics Department.
119
842
N
otices
of
the
AMs
V
oluMe
60, N
uMber
7
Letters to the Editor
the United States realized about the
same time that they wanted intercon-
tinental missiles, and each pursued
its goal knowing very little about
what the other was doing” (Nor-
man Friedman, The Fifty Years War,
p. 232).
Von Neumann’s technical report
written for the Air Force in 1954
helped design the Atlas, but it was
James Killian’s strategic report writ-
ten for President Eisenhower in 1955
that recommended building the
missile. Eisenhower doubted the stra-
tegic value of liquid fuel missiles, and
only 129 Atlas missiles were ever
deployed. Instead, Atlas rockets were
used for space exploration, which
may be another of von Neumann’s
legacies.
—Joseph Grcar
Independent scholar
jfgrcar@gmail.com
(Received May 17, 2013)
Response to Grcar
I am grateful to Joseph Grcar for
clarifying the history of the inter-
continental missile programs of the
United States and the Soviet Union.
I do not find any substantial incon-
sistency between his account of the
history and mine.
—Freeman Dyson
Institute for Advanced Study
dyson@ias.edu
(Received May 18, 2013)
up with their own ideas, opinions and
reactions” in contexts that celebrate
mathematics’ “history, philosophy,
thematic development, aesthetic cri-
teria and current status” (Lockhart,
p. 40). Curriculum materials suf-
ficient to teach ten semester-long
courses on entirely different math-
ematical subject areas are freely
available. Professional development
workshops and other supporting
resources are also available. (See
http://artofmathematics.
westfield.ma.edu.)
Projects like this vividly illustrate
the potential of alternatives, like
Lockhart’s “Mathematical Reality”,
to transform what has been a long
“nightmare” for students into an
intellectual experience in which they
feel “exultation”.
—Julian F. Fleron
Westfield State University
jfleron@westfield.ma.edu
(Received April 11, 2013)
Dyson’s Imagined History
Some portions of Freeman Dyson’s
article about John von Neumann
(Notices, February 2013), as physi-
cists say, are not even wrong. Dyson
imagines that von Neumann began an
arms race by writing a report about
the Atlas rocket.
The actual history is rather dif-
ferent. “The missile race was not the
action-reaction situation so often
imagined. Both the Soviet Union and
John Glenn atop a version of von
Neumann’s Atlas rocket.
Photo credit: NASA.
Submitting Letters to the
Editor
The Notices invites readers to
submit letters and opinion pieces
on topics related to mathemat-
ics. Electronic submissions are
preferred (notices-letters@
ams.org); see the masthead for
postal mail addresses. Opinion
pieces are usually one printed
page in length (about 800 words).
Letters are normally less than one
page long, and shorter letters are
preferred.
Identifications
Affiliations of authors of “Let-
ters to the Editor” are provided
for identification purposes only.
Opinions expressed in letters
are those of the authors and do
not necessarily reflect those of
their employers or, in the case of
American Mathematical Society
officers or committee members,
policies of the Society. Commit-
tee reports to the Council of the
Society and official communica-
tions of officers of the Society,
when published in the Notices, ap-
pear in the section of the Notices
“From the AMS Secretary”.
22
A
MERICAN
M
ATHEMATICAL
S
OCIETY
Contact the AMS Development Offi ce by phone: 401-455-4111
or email: development@ams.org
MathSciNe
t
Mathematical Review
s
The National Mathematical Reviews Subscription Program
expands global access to high-quality mathematical research.
As part of its mission to promote mathematics research around the world, the AMS offers
discounted subscriptions to MathSciNet® to developing nations. For some nations even
the discounted prices are too costly and those countries are fully sponsored through the
program, which currently reaches more than one hundred institutions in over forty
countries. Donor support provides access to mathematics for even more global communities.
Support the National Mathematical Reviews
Subscription Program online at
www.ams.org/support
74
The Computation of
Previously Inaccessible
Digits of
2
and
Catalan’s Constant
David H. Bailey, Jonathan M. Borwein, Andrew Mattingly,
and Glenn Wightwick
Introduction
Werecentlyconcludedavery largemathematical
calculation,uncoveringobjectsthatuntilrecently
werewidely consideredtobeforeverinaccessible
tocomputation.Ourcomputationsstemfromthe
“BBP” formula for , which was discovered in
1997usingacomputerprogramimplementingthe
“PSLQ” integer relation algorithm. This formula
hastheremarkable property thatitpermitsone
todirectlycalculatebinary digitsof,beginning
at an arbitrary position d, without needing to
calculate any ofthefirstd 1digits.Since1997
DavidH.BaileyisseniorscientistattheComputation Re-
search Department of the Lawrence Berkeley National
Laboratory.Hisemailaddressisdhbailey@lbl.gov.
JonathanM.BorweinisprofessorofmathematicsattheCen-
tre forComputerAssistedResearch Mathematics andits
Applications(CARMA),UniversityofNewcastle.Hisemail
addressisjonathan.borwein@newcastle.edu.au.
AndrewMattinglyisseniorinformationtechnologyarchitect
atIBMAustralia.Hisemailaddressisandrew_mattingly@
au1.ibm.com.
GlennWightwickisdirector,IBMResearch–Australia.His
emailaddressisglenn_wightwick@au.ibm.com.
ThefirstauthorwassupportedinpartbytheDirector,
OfficeofComputationalandTechnologyResearch,Division
ofMathematical,Information,andComputationalSciences
oftheU.S.DepartmentofEnergy,undercontractnumber
DE-AC02-05CH11231.
DOI:http://dx.doi.org/10.1090/noti1015
numerous other BBP-type formulas have been
discovered for various mathematical constants,
including formulas for
2
(both in binary and
ternarybases)andforCatalan’sconstant.
In this article we describe the computation
of base-64 digits of 2, base-729 digits of 2,
and base-4096 digits of Catalan’s constant, in
each case beginning at the ten trillionth place,
computationsthatinvolvedatotalofapproximately
1:54910
19
floating-point operations. We also
discuss connections between BBP-type formulas
andtheage-oldunsolvedquestionsofwhetherand
why constantssuchas;2;log 2,andCatalan’s
constant have“random”digits.
HistoricalBackground
Since the dawn of civilization, mathematicians
havebeen intriguedby the digitsof [6], more
sothan anyothermathematicalconstant. In the
thirdcenturyBCE,Archimedesemployedabrilliant
schemeofinscribedandcircumscribed32n-gons
to compute to two decimal digit accuracy.
However,thisandothernumericalcalculationsof
antiquity wereseverelyhobbledbytheirreliance
onprimitivearithmeticsystems.
One of the most significant scientific devel-
opments of history was the discovery of full
positional decimal arithmetic with zero by an
unknown mathematician or mathematicians in
Indiaatleastby500CEandprobablyearlier.Some
844
NoticesoftheAMS
Volume60,Number7
124
oftheearliestdocumentationincludestheAryab-
hatiya,the writingsofthe Indianmathematician
Aryabhata dated to 499 CE; the Lokavibhaga, a
cosmologicalworkwithastronomicalobservations
thatpermitmodernscholarstoconcludethatitwas
writtenon25August458CE[9];andtheBakhshali
manuscript,anancientmathematicaltreatisethat
some scholars believe may be older still, but in
anyeventisnolaterthan theseventhcentury[7],
[8],[2].TheBakhshali manuscriptincludes,among
other things, the following intriguing algorithm
forcomputingthesquareroot ofq,startingwith
anapproximation x
0
:
a
n
q x2
n
2x
n
;
x
n1
x
n
a
n
a
2
n
2x
n
a
n
:
(1)
This scheme is quartically convergentin that it
approximatelyquadruples thenumberofcorrect
digitswith each iteration (although itwas never
iteratedmorethanoncein theexamplesgivenin
themanuscript)[2].
In the tenth century, Gerbertof Aurillac, who
later reigned as Pope Sylvester II, attempted
to introduce decimal arithmetic in Europe, but
little headway wasmadeuntilthepublicationof
Fibonacci’sLiber Abaci in 1202.Severalhundred
moreyearswouldpassbeforethesystemfinally
gaineduniversal,ifbelated,adoptionin theWest.
ThetimeofSylvester’sreignwasavery turbulent
one,andhediedin1003,shortlyafterthedeathof
hisprotector,EmperorOttoIII.It isinterestingto
speculatehowhistorywouldhavechangedhadhe
livedlonger.Apagefromhismathematicaltreatise
DeGeometria isshown inFigure1.
TheAge ofNewton
Armedwithdecimalarithmeticandspurredbythe
newlydiscoveredmethodsof calculus,mathemati-
cianscomputedwithaplomb.Again,thenumerical
value of was a favorite target. Isaac Newton
devisedanarcsine-likeschemetocomputedigitsof
andrecorded15digits,althoughhesheepishly
acknowledged,“Iamashamedtotellyoutohow
manyfiguresIcarriedthesecomputations,having
no other business at the time.” Newton wrote
thesewordsduringtheplague year 1666,when,
ensconced in a country estate, he devised the
fundamentalsofcalculusandthelawsofmotion
andgravitation.
Alllarge computationsof until1980 relied
onvariationsofMachin’sformula:
4
4arctan
1
5
arctan
1
239
:
(2)
Theculminationofthesefeatswasacomputationof
using(2)to527digitsin1853byWilliamShanks,
Figure1.ExcerptfromDeGeometria by Pope
SylvesterII(reigned999–1003CE).
later(erroneously)extendedto 707 digits.Inthe
preface to the publication of this computation,
Shankswrote thathis work“wouldaddlittle or
nothingtohisfame asa Mathematician,though
it might as a Computer” (until 1950 the word
“computer”wasusedforaperson,andtheword
“calculator”wasusedforamachine).
Onemotivation forsuch computationswasto
seewhetherthedigitsof repeat,thusdisclosing
the fact that is a ratio of two integers. This
was settled in 1761, when Lambert provedthat
isirrational,thusestablishingthat thedigits
of donotrepeatin any number base. In 1882
Lindemann establishedthat istranscendental,
thus establishing that the digits of f
2
or any
integerpolynomialof cannotrepeat,andalso
settlingonceandforalltheancientGreekquestion
ofwhetherthecirclecould besquared—itcannot,
because all numbers that can be formed by
finitestraightedge-and-compassconstructionsare
necessarilyalgebraic.
TheComputerAge
At the dawn of the computer age, John von
Neumannsuggestedcomputingdigitsofprominent
mathematical constants, including ande, for
statistical analysis. At his instigation, , was
computedto2,037digitsin1949ontheElectronic
August 2013
NoticesoftheAMS
845
181
DivisionofMedicine&Science,NationalMuseum
ofAmericanHistory,SmithsonianInstitution.
Figure2.TheENIACin theSmithsonian’s
NationalMuseumofAmerican History.
NumericalIntegratorandCalculator(ENIAC);see
Figure 2. In 1965 mathematicians realized that
thenewlydiscoveredfastFouriertransformcould
beusedtodramaticallyacceleratehigh-precision
multiplication, thus facilitating not only large
calculationsofandothermathematicalconstants
butresearchin computationalnumbertheory as
well.
In 1976 Eugene Salamin and Richard Brent
independently discovered new algorithms for
computingtheelementaryexponentialandtrigono-
metricfunctions(andthus constants such as
ande)much morerapidlythanbyusingclassical
seriesexpansions.Theirschemes,basedonelliptic
integralsandtheGaussarithmetic-geometricmean
iteration, approximately double the number of
correct digits in the result with each iteration.
Armedwith such techniques, wascomputed to
overonemilliondigitsin1973,tooveronebillion
digitsin 1989,to overone trillion digitsin2002,
andtooverfivetrillion digitsatthepresenttime;
seeTable1.
Similarly, the constants e;;
p
2;log2;log10,
3,Catalan’sconstantG
P
1
n0
1n=2n12,
andEuler’s
constanthavenow been computed
toimpressivenumbersofdigits;seeTable2[10].
One of the most intriguing aspects of this
historical chronicle is the repeated assurances,
oftenvoicedbyhighlyknowledgeablepeople,that
future progress would be limited. As recently
as 1963, Daniel Shanks, who himself calculated
toover100,000digits,toldPhilipDavis that
computing one billion digits would be “forever
impossible.”Yetthisfeatwasachievedlessthan
thirty years later in 1989 by Yasumasa Kanada
ofJapan. Also in 1989, famous British physicist
Roger Penrose, in the first edition of his best-
selling book TheEmperor’s NewMind, declared
thathumankindlikelywillneverknowifastringof
Table 1.ModernComputer-Era Calculations.
Name
Year
CorrectDigits
MiyoshiandKanada
1981
2,000,036
Kanada-Yoshino-Tamura
1982
16,777,206
Gosper
1985
17,526,200
Bailey
Jan.1986
29,360,111
KanadaandTamura
Sep.1986
33,554,414
KanadaandTamura
Oct.1986
67,108,839
Kanadaet.al
Jan.1987
134,217,700
KanadaandTamura
Jan.1988
201,326,551
Chudnovskys
May1989
480,000,000
KanadaandTamura
Jul.1989
536,870,898
KanadaandTamura
Nov.1989
1,073,741,799
Chudnovskys
Aug.1991
2,260,000,000
Chudnovskys
May1994
4,044,000,000
KanadaandTakahashi
Oct.1995
6,442,450,938
KanadaandTakahashi
Jul.1997
51,539,600,000
KanadaandTakahashi
Sep.1999
206,158,430,000
Kanada-Ushiro-Kuroda
Dec.2002
1,241,100,000,000
Takahashi
Jan.2009
1,649,000,000,000
Takahashi
Apr.2009
2,576,980,377,524
Bellard
Dec.2009
2,699,999,990,000
KondoandYee
Aug.2010
5,000,000,000,000
Table2.Computations ofOtherMathematical
Constants.
Constant
Decimaldigits
Researcher
Date
p
2
1,000,000,000,000
S.Kondo
2010
1,000,000,000,000
A.Yee
2010
e
500,000,000,000
S.Kondo
2010
log2
100,000,000,000
S.Kondo
2011
log10
100,000,000,000
S.Kondo
2011
3
100,000,001,000
A.Yee
2011
G
31,026,000,000
A.YeeandR.Chan
2009
29,844,489,545
A.Yee
2010
tenconsecutive7soccursinthedecimalexpansion
of.Thisstringwasfoundjusteightyearslater,
in 1997, also by Kanada, beginning at position
22,869,046,249. After beingadvisedof this fact
byoneofthepresentauthors,Penroserevisedhis
secondedition tospecifytwentyconsecutive7s.
Alongthisline,BrouwerandHeyting,exponents
ofthe“intuitionist” schoolofmathematicallogic,
proposed,asa premier example ofa hypothesis
that could neverbeformallysettled,thequestion
ofwhetherthestring“0123456789”appearsinthe
decimalexpansionof.Kanadafoundthisatthe
17,387,594,880-thpositionafterthedecimalpoint.
EvenastronomerCarlSagan,whoseleadcharacter
inhis1985novelContact (playedbyJodiFosterin
themovieversion)soughtconfirmationinbase-11
digits of, expressedsurprise to learn, shortly
after the book’spublication, that t hadalready
beencomputedtomanymillionsofdigits.
TheBBP Formula for pi
A1997paper[3],[5,Ch.3]by oneofthepresent
authors(Bailey),PeterBorweinand Simon Plouffe
presentedthefollowingunknownformulafor,
846
NoticesoftheAMS
Volume60,Number7
258
nowknownasthe“BBP” formulafor:
(3)
X1
k0
1
16k
4
8k1
2
8k4
1
8k5
1
8k6
:
This formula has the remarkable property that
it permits one to directly calculate binary or
hexadecimaldigitsof beginningat anarbitrary
starting position without needing to calculate
anyoftheprecedingdigits.Theresultingsimple
algorithmrequiresonlyminimalmemory,doesnot
requiremultiple-precisionarithmetic,andisvery
well suited to highly parallel computation. The
costofthisschemeincreasesonly slightlyfaster
thantheindexofthestartingposition.
The proof of this formula is surprisingly
elementary.Firstnotethatforany k<8,
(4)
Z
1=
p
2
0
x
k 1
1 x8
dx
Z
1=
p
2
0
X1
i0
x
k 18i
dx
1
2k=2
X1
i0
1
16i8ik
:
Thusonecanwrite
(5)
X1
i0
1
16i
4
8i1
2
8i4
1
8i5
1
8i6
Z
1=
p
2
0
4
p
2 8x
3
4
p
2x
4
8x
5
1 x8
dx;
whichonsubstitutingy:
p
2xbecomes
(6)
Z
1
0
16y 16
y4 2y3 4y 4
dy
Z
1
0
4y
y2 2
dy
Z
1
0
4y 8
y2 2y2
dy ;
reflectingapartialfractiondecomposition ofthe
integralontheleft-handside.In1997neitherMaple
norMathematica couldevaluate(3)symbolically
toproducetheresult.Todayboth systemscan
dothiseasily.
BinaryDigitsoflog2
ItisworthnotingthattheBBPformula(3)wasnot
discoveredbya conventionalanalyticderivation.
Instead, it wasdiscoveredvia a computer-based
search using the PSLQ integer relation detection
algorithm(seethesection“HuntforapiFormula”)
ofmathematician-sculptorHelamanFerguson[4]
in a process that some have described as an
exercise in “reverse mathematical engineering”.
The motivation for this search was the earlier
observationbytheauthorsof[3]thatlog 2alsohas
thisarbitrary position digitcalculatingproperty.
Thiscanbeseenbyanalyzingtheclassicformula
log2
X1
k1
1
k2k
;
(7)
which hasbeen known atleastsincethetimeof
Eulerandwhichiscloselyrelatedtothefunctional
equationforthedilogarithm.
Letr mod 1denotethefractional partofanon-
negativerealnumberr,andletdbeanonnegative
integer.Thenthebinaryfractionoflog 2afterthe
“decimal” point has been shifted to the right d
placescanbewrittenas
(8)
2
d
log2mod 1
0
@
Xd
k1
2
d k
k
mod1
1X
kd1
2
d k
k
mod1
1
A
mod1
0
@
Xd
k1
2
d k
modk
k
mod1
X1
kd1
2d k
k
mod1
1
A
mod 1;
where“modk”hasbeeninsertedinthenumerator
ofthefirsttermsinceweareonlyinterestedinthe
fractionalpartoftheresultafterdivision.
The operation 2
d k
modk can be e performed
very rapidly by means of the binaryalgorithm
for exponentiation. This scheme is the simple
observationthatanexponentiationoperationsuch
as317canbeperformedinonlyfivemultiplications
insteadof16bywritingitas3
17
3
2
2
2
2
3.
Additional savingscanberealized byreducingall
oftheintermediatemultiplicationresultsmodulo
kateachstep.Thisalgorithm,togetherwiththe
divisionandsummationoperationsindicatedinthe
firstterm, can be performedin ordinary double-
precision floating-point arithmetic or for very
largecalculationsbyusingquad-oroct-precision
arithmetic.
Expressingthe finalfractionalvaluein binary
notationyieldsastringofdigitscorrespondingto
the binary digits oflog 2 beginningimmediately
afterthefirstd digitsoflog 2.Computedresults
canbeeasilycheckedbyperformingthisoperation
fortwoslightlydifferentpositions,sayd 1and
d,thencheckingtoseethatresultingdigitstrings
properlyoverlap.
Huntfor apiFormula
In the wake offindingthe above scheme forthe
binarydigitsoflog 2,theauthorsof[3]immediately
wondered if there was a similar formula for
(nonewasknownat thetime).Theirapproachwas
tocollect alistof mathematicalconstants
i
for
whichformulassimilarinstructuretotheformula
forlog 2wereknownintheliteratureand then to
determineby meansofthe PSLQintegerrelation
algorithmifthereexistsanontriviallinearrelation
oftheform
(9)
a
0
a
1
1
a
2
2
a
n
n
0;
August 2013
NoticesoftheAMS
847
130
where a
i
are integers (because such a relation
couldthen be solved for to yield the desired
formula).Afterseveralmonthsoffalsestarts,the
followingrelationwasdiscovered:
(10)
4
2
F
1
0
@
1;
1
4
5
4
1
4
1
A
2arctan
1
2
log5;
where the first term is a Gauss hypergeometric
function evaluation. After writing this formula
explicitlyintermsofsummations,theBBPformula
for wasuncovered:
(11)
X1
k0
1
16k
4
8k1
2
8k4
1
8k5
1
8k6
:
One question that immediately arose in the
wake of the discovery ofthe BBP formula for
waswhetherthereareformulasofthistypefor
inothernumberbases—in otherwords,formulas
wherethe16intheBBPformulaisreplacedbysome
other integer, such as 3 or 10. These computer
searcheswerelargelylaidtorestin2004,whenone
ofthepresentauthors(JonathanBorwein),together
withWillGalwayandDavidBorwein,showedthat
therearenodegree-1BBP-typeformulasofMachin-
typefor,exceptthosewhosebaseisapowerof
two[5,pp.131–133].
TheBBPFormulainAction
Variants of the BBP formula have been used
in numerous computations of high-index digits
of . In 1998 Colin Percival, then a 17-year-
old undergraduate at Simon Fraser University
in Canada, computedbinary digits beginning at
position onequadrillion (10
15
).Atthe time,this
wasoneofthelargest,ifnotthelargest,distributed
computations ever done. More recently, in July
2010,Tsz-WoSzeofYahoo!CloudComputing,in
roughly500 CPU-years ofcomputingon Apache
Hadoop clusters,found thatthebase-16digitsof
beginningatposition51014 (corresponding
tobinary positiontwoquadrillion)are
0 E6C1294A ED40403F 56D2D764 026265BC
A98511D0 FCFFAA10 F4D28B1B B5392B8
Inan even morerecent2013computation along
thisline,EdKarrelsofSantaClaraUniversityuseda
systemwithNVIDIAgraphicscardstocompute26
base-16digitsbeginningatpositiononequadrillion.
Hisresult:8353CB3F7F0C9ACCFA9AA215F2.
The BBP formulas have also been used to
confirmothercomputationsof.Forexample,in
August2010,ShigeruKondo(ahardwareengineer)
and Alexander Yee (an undergraduate software
engineer)computedfivetrilliondecimaldigitsof
onahome-built$18,000machine.Theyfound
thatthe last thirty digits leading up to position
fivetrillionare
Figure3.(T)ShigeruKondoandhis-computer.
(B)AlexYeeandhiselephant.
7497120374 4023826421 9484283852
KondoandYee(seeFigure3)usedthefollowing
Chudnovsky-Ramanujanseries:
(12)
1
12
X1
k0
1k6k!13591409545140134k
3k!k!36403203k3=2
:
They did not merely evaluate this formula as
written but instead employed a clever quasi-
symbolicschemethat mostlyavoidstheneedfor
full-precision arithmetic.
Kondo and Yee firstcomputed their resultin
hexadecimal (base-16) digits. Then, in a crucial
verificationstep,theycheckedhex digitsnearthe
endagainst the same string of digits computed
usingtheBBPformulafor.Whenthistestpassed,
they convertedtheirentireresulttodecimal.The
entire computation took ninety days, including
sixty-fourhoursfortheBBPconfirmationandeight
daysforbaseconversion todecimal.Notethatthe
muchlowertimefortheBBPconfirmation,relative
totheothertwoparts,greatlyreducedtheoverall
computationalcost.Adescriptionoftheirworkis
availableat[11].
848
NoticesoftheAMS
Volume60,Number7
228
BBP-Type Formulasfor Other Constants
In the years since 1997, computer searches
using the PSLQ algorithm, as well as conven-
tional analytic investigations, have uncovered
BBP-type formulas for numerous other math-
ematical constants, including g 2;log
2
2;log 2,
3;3;log
3
2;2log 2;4;5 and Catalan’s
constant.BBPformulasarealsoknown formany
arctangents, as well as forlogk; 2k 22, al-
thoughnoneisknownforlog 23.Theseformulas
and many others, together with references, are
giveninan onlinecompendium[1].
Oneparticularlyintriguingfactisthat,whereas
only binary formulasexistfor, there are both
binaryandternary(base-3)formulasfor
2
:
2
9
8
X1
k0
1
64k
16
6k12
24
6k22
8
6k32
(13)
6
6k42
1
6k52
;
2
2
27
X1
k0
1
729k
243
12k12
405
12k22
(14)
81
12k42
27
12k52
72
12k62
9
12k72
9
12k82
5
12k102
1
12k112
:
Formula(13)appearedin[3],whileformula(14)
isduetoBroadhurst.ThereareknownbinaryBBP
formulas for both3 and
3
,but no one has
foundaternaryformulaforeither.
Catalan’sConstant
Oneothermathematicalconstantofcentralinterest
isEugéneCharlesCatalan’s(1814–1894) constant,
(15)
G
X1
n0
1n
2n12
0:91596559417722:::;
which isarguablythemostbasicconstantwhose
irrationality andtranscendence(though strongly
suspected) remain unproven. Note the close
connectiontothisformulafor
2
:
(16)
2
8
X1
n0
1
2n12
1:2337005501362::::
Formulas(15)and(16)canbeviewedasthesimplest
DirichletL-seriesvaluesat2.Suchconsiderations
werebehindourdecisiontofocusthecomputation
described inthispaperon thesetwoconstants.
Catalan’s constant has already been the sub-
ject of some large computations. As mentioned
above,in2009AlexanderYeeandRaymond Chan
calculated G to 31.026 billion digits [10]. This
computation employedtwo formulas, including
thisformuladuetoRamanujan:
(17) G
3
8
1X
n0
1
2n
n
2n12
8
log2
p
3;
whichcanbederivedfromthefact that
G T=4 3=2T=12;
whereT:
R
0
logtan d.
TheBBPcompendiumliststwoBBP-typeformu-
lasforG.Thefirst wasdiscoverednumericallyby
Bailey, butboth itandthe second formula were
subsequentlyprovenbyKunleAdegoke,basedin
parton someresultsofBroadhurst.
Forthepresentstudy,wesoughtaformulaforG
withasfewtermsaspossible,becausetheruntime
forcomputingwithaBBP-typeformulaincreases
roughly linearly with the number of nonzero
coefficients.Thetwoformulasinthecompendium
havetwenty-twoandeighteennonzerocoefficients,
respectively. So we explored, by means of a
computation involving the PSLQ algorithm, the
linearspaceofformulasforGspannedby these
twosetsofcoefficients,togetherwithtwoknown
“zero relations” (BBP-type formulas whose sum
is zero). These analyses and computations led
tothefollowingformula,whichhasonlysixteen
nonzerocoefficientsandwhichwebelievetobethe
mosteconomicalBBP-typeformulaforcomputing
Catalan’sconstant:
G
1
4096
X1
k0
1
4096k
36864
24k22
30720
24k32
(18)
30720
24k42
6144
24k62
1536
24k72
2304
24k92
2304
24k102
768
24k142
480
24k152
384
24k112
1536
24k122
24
24k192
120
24k202
36
24k212
48
24k222
6
24k232
:
BBP FormulasandNormality
Oneprimemotivationincomputing andanalyzing
digits of and other well-known mathematical
constantsthroughtheagesistoexploretheage-old
questionofwhetherandwhythesedigitsappear
“random”.Numerouscomputer-basedstatistical
checks ofthe digitsof—unlike those ofe—so
far have failed to disclose any deviation from
reasonable statistical norms. See, for instance,
Table 3,whichpresents the counts ofindividual
August 2013
NoticesoftheAMS
849
173
hexadecimal digits among the first trillion hex
digits,asobtained byYasumasa Kanada.
Givensomepositiveintegerb,arealnumberis
saidtobeb-normalifeverym-longstringofbase-b
digitsappearsin the base-b expansionof with
precisely theexpectedlimitingfrequency1=bm.It
followsfrombasicprobabilitytheory that almost
all real numbers are b-normal for any specific
basebandevenforallbasessimultaneously.But
provingnormalityforspecificconstantsofinterest
inmathematicshasprovenremarkably difficult.
InterestinBBP-typeformulaswasheightenedby
the2001observation,byoneofthepresentauthors
(Bailey)andRichardCrandall,thatthenormality
ofBBP-type constantssuch as;2;log 2 andG
can bereducedtoacertain hypothesisregarding
the behavior of a class of chaotic iterations [5,
pp.141–173].Noproofisknownforthisgeneral
hypothesis, but even specific instances of this
resultwouldbequiteinteresting.Forexample,if
it couldbeestablishedthat theiterationgivenby
w
0
0and
(19)
w
n
2w
n 1
1
n
mod1
is equidistributedin0;1 (i.e.,isa“good”pseu-
dorandomnumbergenerator),then,accordingto
the Bailey-Crandall result, it would follow that
log2is2-normal.Inasimilarvein,ifitcouldbe
establishedthattheiterationgivenbyx
0
0and
(20) x
n
16x
n 1
120n
2
89n16
512n4 1024n3 712n2 206n21
!
mod1
is equidistributedin0;1,then itwouldfollow
that is2-normal.
Givingfurtherhopetothesestudiesistherecent
extension of these methods to a rigorous proof
ofnormality foran uncountably infiniteclassof
realnumbers.Givena realnumberr in0;1,let
r
k
denotethek-thbinarydigitofr.Thenthereal
number
(21)
2;3
r
X1
k0
1
3k23
kr
k
is2-normal. Forexample,the constant
2;3
0
P
k0
1=3k23
k
0:541883680831502985::: : is
provably 2-normal. A similar result applies if 2
and 3 in this formula are replaced by any pair
of coprime integers b;c greater than one [5,
pp.141–173].
ACuriousHexadecimalConjecture
Itistantalizingthatif,using(20),onecalculates
thehexadecimaldigitsequence
(22)
y
n
b16x
n
c
Table3.Digitcounts in thefirsttrillion
hexadecimal(base-16)digitsof.Notethat
deviationsfromthe averagevalue
62,500,000,000occuronly afterthefirstsix
digits,asexpected.
HexDigit
Occurrences
0
62499881108
1
62500212206
2
62499924780
3
62500188844
4
62499807368
5
62500007205
6
62499925426
7
62499878794
8
62500216752
9
62500120671
A
62500266095
B
62499955595
C
62500188610
D
62499613666
E
62499875079
F
62499937801
Total
1000000000000
(where bc denotes greatest integer), then the
sequence y
n
appears to o perfectly y (not just
approximately)producethehexadecimalexpansion
of. In explicit computations, we checked that
thefirst10,000,000hexadecimal digitsgenerated
by this sequence are identical with the first
10,000,000hexadecimaldigitsof 3.Thisisa
fairlydifficult computation,asit requiresroughly
n2 bit-operationsandisnoteasilyperformedona
parallel computersystem.In ourimplementation,
computing2;000;000 hex digitswith(22)using
Maple,required17.3hoursonalaptop.Computing
4,100,000usingMathematica,withamorerefined
implementation, required 46.5 hours. The full
confirmation usinga C++programtook433,192
seconds (120.3 hours) on an IBM Power 780
(model: 9179-MHB, clock speed: 3.864 GHz). All
theseoutputswereconfirmedagainst storedhex
digits of in the software section of http:
//www.experimentalmath.info.
Conjecture1. Thesequenceb16x
n
c,where x
n
is
thesequence of iterates defined in equation (20),
generatespreciselythehexadecimalexpansionof
3.
We can learn more. Let jjx yjj minjx
yj;j1 x yjdenotethe“wrapped”distance
between reals s x and y in n 0;1. The base-16
850
NoticesoftheAMS
Volume60,Number7
Documents you may be interested
Documents you may be interested
