Modern Computer ArithmeticModern Computer Arithmetic focuses on arbitrary-precision 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), and the computation of elementary and special functions. Brent and Zimmermann present algorithms that are ready to implement in your favourite language, while keeping a high-level description and avoiding too low-level or machine-dependent details. The book is intended for anyone interested in the design and implementation of efficient high-precision algorithms for computer arithmetic, and more generally efficient multiple-precision numerical algorithms. It may also be used in a graduate course in mathematics or computer science, for which exercises are included. These vary considerably in difficulty, from easy to small research projects, and expand on topics discussed in the text. Solutions to selected exercises are available from the authors. |
Common terms and phrases
AGM iteration approximation arbitrary-precision arbitrary-precision arithmetic argument reduction assume asymptotic expansion B₁ BasecaseDivRem bc bc bc Bernoulli numbers binary splitting Brent Chapter classical coefficients complex compute consider constant continued fraction converges correct rounding cost defined division divisor efficient encoding erf(x evaluate exact example Exercise exp(x exponent exponentiation fast FFT range floating-point arithmetic floating-point numbers formula Fourier transform gives guard digits Horner's rule IEEE implementation Input integer inverse Karatsuba Lemma mathematical middle product mod 2n modular arithmetic modular exponentiation modulo Montgomery reduction MPFR multiplication algorithms n-bit Newton's method operands operations Output performed polynomial power series precision precomputed quotient radix reciprocal recurrence remainder representation residue number system rounding mode rounding to nearest Schönhage-Strassen algorithm short product significand significant bits square root ẞk step subquadratic subtraction tangent numbers Theorem Toom-Cook truncated vector words Xj+1 zero