For a computer algebra system, it is crucial to optimize the arithmetical operations on basic objectsnumbers, polynomials, series, ... In fact, two classes of objects can be distinguished: integers and polynomials, which require exact operations; floatingpoint numbers and series, for which only the most significant part of the exact result is needed. The best algorithms currently known for multiplication, division, and square root on integers and floatingpoint numbers are mostly recent. We present and analyse them using complexity models based on three different multiplication algorithms (naive, Karatsuba, and FFT).
The MPFR library developed by Guillaume Hanrot and Paul Zimmermann is a C library for multiprecision floatingpoint computations with exact rounding [6]. Its main purpose is to achieve efficiency with a welldefined semantics. Beside the elementary operations +, , ×, and /, it provides routines for square root (with remainder in the integer case, without remainder in the floatingpoint case), logarithm and exponential. The longerterm goal is to integrate routines for the numerical evaluation of other elementary and special functions as well.
Operation Naive Karatsuba FFT Method exact truncated exact truncated exact truncated Multiplication 1 1/2 1 1 1 1 Mulders 0.808 Division 1 1/2 Newton 7/2 5/2 5 4 KarpMarkstein 17/6 11/6 9/2 7/2 Jebelean, BurnikelZiegler 2 3/2 Mulders 1.397 Square root 1/2 1/4 Newton 7/2 5/2 5 4 KarpMarkstein 17/6 11/6 9/2^{'} 7/2^{'} Jebelean, BurnikelZiegler 3/2^{''} 1^{''} Mulders 0.966^{''}
Figure 1: Complexity of division and square root algorithms in terms of exact multiplications for the three usual multiplication models. Algorithms marked `'', resp. `''', were analysed, resp. designed and analysed, by Paul Zimmermann in [8].
uv=(u_{1}b+u_{0})(v_{1}b+v_{0}) =u_{1}v_{1}b^{2}+  (  (u_{1}+v_{1})(u_{0}+v_{0})u_{1}v_{1}u_{0}v_{0}  )  b+u_{0}v_{0}, (1) 
i 
æ ç ç è 

ö ÷ ÷ ø 
= 

and r 
æ ç ç è 

ö ÷ ÷ ø 
= 

. 
http://www.inria.fr/RRRT/RR3973.html
.http://www.loria.fr/projets/mpfr/
.This document was translated from L^{A}T_{E}X by H^{E}V^{E}A.