Modern Computer Arithmetic RichardP.BrentandPaulZimmermann Version0.5.1of5March2010 iii Copyright c 2003-2010RichardP.BrentandPaulZimmermann ° Thiselectronicversionisdistributedunderthetermsandconditionsofthe CreativeCommonslicense“Attribution-Noncommercial-NoDerivativeWorks 3.0”.Youarefreetocopy,distributeandtransmitthisbookunderthefollowing conditions: Attribution. You must attribute the work in the manner specified by the • authororlicensor(butnotinanywaythatsuggeststhattheyendorseyouor youruseofthework). Noncommercial.Youmaynotusethisworkforcommercialpurposes. • No Derivative Works. You may not alter, transform, or build upon this • work. Foranyreuseordistribution,youmustmakecleartoothersthelicenseterms ofthiswork.Thebestwaytodothisiswithalinktothewebpagebelow.Any oftheaboveconditionscanbewaivedifyougetpermissionfromthecopyright holder.Nothinginthislicenseimpairsorrestrictstheauthor’smoralrights. Formoreinformationaboutthelicense,visit http://creativecommons.org/licenses/by-nc-nd/3.0/ Contents Preface pageix Acknowledgements xi Notation xiii 1 IntegerArithmetic 1 1.1 RepresentationandNotations 1 1.2 AdditionandSubtraction 2 1.3 Multiplication 3 1.3.1 NaiveMultiplication 4 1.3.2 Karatsuba’sAlgorithm 5 1.3.3 Toom-CookMultiplication 6 1.3.4 UseoftheFastFourierTransform(FFT) 8 1.3.5 UnbalancedMultiplication 8 1.3.6 Squaring 11 1.3.7 MultiplicationbyaConstant 13 1.4 Division 14 1.4.1 NaiveDivision 14 1.4.2 DivisorPreconditioning 16 1.4.3 DivideandConquerDivision 18 1.4.4 Newton’sMethod 21 1.4.5 ExactDivision 21 1.4.6 OnlyQuotientorRemainderWanted 22 1.4.7 DivisionbyaSingleWord 23 1.4.8 Hensel’sDivision 24 1.5 Roots 25 1.5.1 SquareRoot 25 1.5.2 k-thRoot 27 1.5.3 ExactRoot 28 Contents v 1.6 GreatestCommonDivisor 29 1.6.1 NaiveGCD 29 1.6.2 ExtendedGCD 32 1.6.3 HalfBinaryGCD,DivideandConquerGCD 33 1.7 BaseConversion 37 1.7.1 QuadraticAlgorithms 37 1.7.2 SubquadraticAlgorithms 38 1.8 Exercises 39 1.9 NotesandReferences 44 2 ModularArithmeticandtheFFT 47 2.1 Representation 47 2.1.1 ClassicalRepresentation 47 2.1.2 Montgomery’sForm 48 2.1.3 ResidueNumberSystems 48 2.1.4 MSBvsLSBAlgorithms 49 2.1.5 LinkwithPolynomials 49 2.2 ModularAdditionandSubtraction 50 2.3 TheFourierTransform 50 2.3.1 TheoreticalSetting 50 2.3.2 TheFastFourierTransform 51 2.3.3 TheScho¨nhage-StrassenAlgorithm 55 2.4 ModularMultiplication 58 2.4.1 Barrett’sAlgorithm 58 2.4.2 Montgomery’sMultiplication 60 2.4.3 McLaughlin’sAlgorithm 64 2.4.4 SpecialModuli 65 2.5 ModularDivisionandInversion 65 2.5.1 SeveralInversionsatOnce 67 2.6 ModularExponentiation 68 2.6.1 BinaryExponentiation 70 2.6.2 ExponentiationWithaLargerBase 71 2.6.3 SlidingWindowandRedundantRepresentation 72 2.7 ChineseRemainderTheorem 73 2.8 Exercises 75 2.9 NotesandReferences 77 3 Floating-PointArithmetic 81 3.1 Representation 81 3.1.1 RadixChoice 82 3.1.2 ExponentRange 83 vi Contents 3.1.3 SpecialValues 84 3.1.4 SubnormalNumbers 84 3.1.5 Encoding 85 3.1.6 Precision:Local,Global,Operation,Operand 86 3.1.7 LinktoIntegers 87 3.1.8 Ziv’sAlgorithmandErrorAnalysis 88 3.1.9 Rounding 89 3.1.10 Strategies 93 3.2 Addition,Subtraction,Comparison 93 3.2.1 Floating-PointAddition 94 3.2.2 Floating-PointSubtraction 96 3.3 Multiplication 97 3.3.1 IntegerMultiplicationviaComplexFFT 101 3.3.2 TheMiddleProduct 102 3.4 ReciprocalandDivision 104 3.4.1 Reciprocal 104 3.4.2 Division 108 3.5 SquareRoot 113 3.5.1 ReciprocalSquareRoot 114 3.6 Conversion 117 3.6.1 Floating-PointOutput 117 3.6.2 Floating-PointInput 120 3.7 Exercises 120 3.8 NotesandReferences 122 4 ElementaryandSpecialFunctionEvaluation 127 4.1 Introduction 127 4.2 Newton’sMethod 128 4.2.1 Newton’sMethodforInverseRoots 129 4.2.2 Newton’sMethodforReciprocals 130 4.2.3 Newton’sMethodfor(Reciprocal)SquareRoots 131 4.2.4 Newton’sMethodforFormalPowerSeries 131 4.2.5 Newton’sMethodforFunctionalInverses 132 4.2.6 HigherOrderNewton-likeMethods 133 4.3 ArgumentReduction 134 4.3.1 RepeatedUseofaDoublingFormula 136 4.3.2 LossofPrecision 136 4.3.3 GuardDigits 137 4.3.4 DoublingversusTripling 138 4.4 PowerSeries 138 Contents vii 4.4.1 DirectPowerSeriesEvaluation 142 4.4.2 PowerSeriesWithArgumentReduction 142 4.4.3 RectangularSeriesSplitting 143 4.5 AsymptoticExpansions 146 4.6 ContinuedFractions 152 4.7 RecurrenceRelations 154 4.7.1 EvaluationofBesselFunctions 155 4.7.2 EvaluationofBernoulliandTangentnumbers 156 4.8 Arithmetic-GeometricMean 160 4.8.1 EllipticIntegrals 160 4.8.2 FirstAGMAlgorithmfortheLogarithm 161 4.8.3 ThetaFunctions 162 4.8.4 SecondAGMAlgorithmfortheLogarithm 164 4.8.5 TheComplexAGM 165 4.9 BinarySplitting 166 4.9.1 ABinarySplittingAlgorithmforsin,cos 168 4.9.2 TheBit-BurstAlgorithm 169 4.10 ContourIntegration 171 4.11 Exercises 173 4.12 NotesandReferences 181 5 ImplementationsandPointers 187 5.1 SoftwareTools 187 5.1.1 CLN 187 5.1.2 GNUMP(GMP) 187 5.1.3 MPFQ 188 5.1.4 MPFR 189 5.1.5 OtherMultiple-PrecisionPackages 189 5.1.6 ComputationalAlgebraPackages 190 5.2 MailingLists 191 5.2.1 TheBNISMailingList 191 5.2.2 TheGMPLists 192 5.2.3 TheMPFRList 192 5.3 On-lineDocuments 192 Bibliography 195 Index 211 SummaryofComplexities 227 Preface This is a book about algorithms for performing arithmetic, and their imple- mentation on modern computers. We are concerned with software more than hardware — we do not cover computer architecture or the design of com- puterhardwaresincegoodbooksarealreadyavailableonthesetopics.Instead we focus on algorithms for efficiently performing arithmetic operations such as addition, multiplication and division, and their connections to topics such as modular arithmetic, greatest common divisors, the Fast Fourier Transform (FFT),andthecomputationofspecialfunctions. The algorithms that we present are mainly intended for arbitrary-precision arithmetic.Thatis,theyarenotlimitedbythecomputerwordsizeof32or64 bits,onlybythememoryandtimeavailableforthecomputation.Weconsider bothintegerandreal(floating-point)computations. Thebookisdividedintofourmainchapters,plusoneshortchapter(essen- tially an appendix). Chapter 1 covers integer arithmetic. This has, of course, been considered in many other books and papers. However, there has been much recent progress, inspired in part by the application to public key cryp- tography,somostofthepublishedbooksarenowpartlyoutofdateorincom- plete.Ouraimistopresentthelatestdevelopmentsinaconcisemanner.Atthe sametime,weprovideaself-containedintroductionforthereaderwhoisnot anexpertinthefield. Chapter2isconcernedwithmodulararithmeticandtheFFT,andtheirappli- cationstocomputerarithmetic.Weconsiderdifferentnumberrepresentations, fastalgorithmsformultiplication,divisionandexponentiation,andtheuseof theChineseRemainderTheorem(CRT). Chapter 3 covers floating-point arithmetic. Our concern is with high- precision floating-point arithmetic, implemented in software if the precision provided by the hardware (typically IEEE standard 53-bit significand) is x Preface inadequate. The algorithms described in this chapter focus on correct round- ing,extendingtheIEEEstandardtoarbitraryprecision. Chapter 4 deals with the computation, to arbitrary precision, of functions suchassqrt,exp,ln,sin,cos,andmoregenerallyfunctionsdefinedbypower seriesorcontinuedfractions.Ofcourse,thecomputationofspecialfunctionsis ahugetopicsowehavehadtobeselective.Inparticular,wehaveconcentrated onmethodsthatareefficientandsuitableforarbitrary-precisioncomputations. The last chapter contains pointers to implementations, useful web sites, mailing lists, and so on. Finally, at the end there is a one-page Summary of Complexitieswhichshouldbeausefulaide-me´moire. The chapters are fairly self-contained, so it is possible to read them out of order.Forexample,Chapter4couldbereadbeforeChapters1–3,andChapter 5 can be consulted at any time. Some topics, such as Newton’s method, ap- pear in different guises in several chapters. Cross-references are given where appropriate. For details that are omitted we give pointers in the Notes and References sections of each chapter, as well as in the bibliography. We have tried, as far aspossible,tokeepthemaintextunclutteredbyfootnotesandreferences,so mostreferencesaregivenintheNotesandReferencessections. Thebookisintendedforanyoneinterestedinthedesignandimplementation of efficient algorithms for computer arithmetic, and more generally efficient numericalalgorithms.Wedidourbesttopresentalgorithmsthatarereadyto implement in your favorite language, while keeping a high-level description and not getting too involved in low-level or machine-dependent details. An alphabeticallistofalgorithmscanbefoundintheindex. Although the book is not specifically intended as a textbook, it could be used in a graduate course in mathematics or computer science, and for this reason, as well as to cover topics that could not be discussed at length in the text,wehaveincludedexercisesattheendofeachchapter.Theexercisesvary considerably in difficulty, from easy to small research projects, but we have notattemptedtoassignthemanumericalrating.Forsolutionstotheexercises, pleasecontacttheauthors. We welcome comments and corrections. Please send them to either of the authors. RichardBrentandPaulZimmermann [email protected] [email protected] CanberraandNancy,February2010