Elementary_Functions-Muller-2e.pdf

(2672 KB) Pobierz
583803427 UNPDF
583803427.001.png
Jean-Michel Muller
Elementary Functions
Algorithms and Implementation
Second Edition
Birkhauser
Boston • Basel • Berlin
583803427.002.png
Jean-Michel Muller
CNRS-Laboratoire LIP
Ecole Normale Superieure de Lyon
46 allee d’Italie
69364 Lyon Cedex 07
France
Cover design by Joseph Sherman.
AMS Subject Classifications: 26A09, 33Bxx, 90Cxx, 65D15, 65K05, 68Wxx, 65Yxx
ACM Subject Classifications: B.2.4, G.1.0., G.1.2, G.4
Library of Congress Cataloging-in-Publication Data
Muller, J. M. (Jean-Michel), 1961-
Elementary functions : algorithms and implementation / Jean-Michel Muller.– 2nd ed.
p. cm.
Includes bibliographical references and index.
ISBN 0-8176-4372-9 (alk. paper)
1. Functions–Data processing 2. Algorithms. I. Title.
QA331.M866 2005
518 .1–dc22
2005048094
ISBN-10 0-8176-4372-9
eISBN 0-8176-4408-3
Printed on acid-free paper.
ISBN-13 978-0-8176-4372-0
2006 Birkhauser Boston, 2nd edition
c
1997 Birkhauser Boston, 1st Edition
All rights reserved. This work may not be translated or copied in whole or in part without the written permission of the
publisher (Birkhauser Boston, c/o Springer Science + Business Media Inc., 233 Spring Street, New York, NY 10013,
USA), except for brief excerpts in connection with reviews or scholarly analysis. Use in connection with any form of
information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology
now known or hereafter developed is forbidden.
The use in this publication of trade names, trademarks, service marks and similar terms, even if they are not identified
as such, is not to be taken as an expression of opinion as to whether or not they are subject to proprietary rights.
Printed in the United States of America.
(LAP/HP)
987654321
www.birkhauser.com
c
583803427.003.png
Contents
List of Figures
xi
List of Tables
xv
Preface to the Second Edition
xix
Preface to the First Edition
xxi
1 Introduction
1
2 Some Basic Things About Computer Arithmetic 9
2.1 Floating-Point Arithmetic ....................... 9
2.1.1 Floating-point formats ..................... 9
2.1.2 Rounding modes ........................ 11
2.1.3 Subnormal numbers and exceptions ............. 13
2.1.4 ULPs ............................... 14
2.1.5 Fused multiply-add operations ................ 15
2.1.6 Testing your computational environment .......... 16
2.1.7 Floating-point arithmetic and proofs ............. 17
2.1.8 Maple programs that compute double-precision
approximations ......................... 17
2.2 Redundant Number Systems ..................... 19
2.2.1 Signed-digit number systems ................. 19
2.2.2 Radix-2 redundant number systems ............. 21
I Algorithms Based on Polynomial Approximation and/or
Table Lookup, Multiple-Precision Evaluation of Functions
25
3 Polynomial or Rational Approximations 27
3.1 Least Squares Polynomial Approximations ............. 28
3.1.1 Legendre polynomials ..................... 29
3.1.2 Chebyshev polynomials .................... 29
3.1.3 Jacobi polynomials ....................... 31
vi
Contents
3.1.4 Laguerre polynomials ..................... 31
3.1.5 Using these orthogonal polynomials in any interval .... 31
3.2 Least Maximum Polynomial Approximations ............ 32
3.3 Some Examples ............................. 33
3.4 Speed of Convergence ......................... 39
3.5 Remez’s Algorithm ........................... 41
3.6 Rational Approximations ........................ 46
3.7 Actual Computation of Approximations ............... 50
3.7.1 Getting “general” approximations .............. 50
3.7.2 Getting approximations with special constraints ...... 51
3.8 Algorithms and Architectures for the Evaluation of Polynomials . 54
3.8.1 The E-method .......................... 57
3.8.2 Estrin’s method ......................... 58
3.9 Evaluation Error Assuming Horner’s Scheme is Used ....... 59
3.9.1 Evaluation using floating-point additions and
multiplications ......................... 60
3.9.2 Evaluation using fused multiply-accumulate
instructions ........................... 64
3.10 Miscellaneous .............................. 66
4 Table-Based Methods 67
4.1 Introduction ............................... 67
4.2 Table-Driven Algorithms ........................ 70
4.2.1 Tang’s algorithm for exp( x ) in IEEE floating-point arithmetic 71
4.2.2 ln( x ) on [1 , 2] .......................... 72
4.2.3 sin( x ) on [0 ,π/ 4] ........................ 73
4.3 Gal’s Accurate Tables Method ..................... 73
4.4 Table Methods Requiring Specialized Hardware .......... 77
4.4.1 Wong and Goto’s algorithm for computing
logarithms ............................ 78
4.4.2 Wong and Goto’s algorithm for computing
exponentials ........................... 81
4.4.3 Ercegovac et al.’s algorithm .................. 82
4.4.4 Bipartite and multipartite methods .............. 83
4.4.5 Miscellaneous .......................... 87
5 Multiple-Precision Evaluation of Functions 89
5.1 Introduction ............................... 89
5.2 Just a Few Words on Multiple-Precision Multiplication ...... 90
5.2.1 Karatsuba’s method ...................... 91
5.2.2 FFT-based methods ....................... 92
5.3 Multiple-Precision Division and Square-Root ............ 92
5.3.1 Newton–Raphson iteration .................. 92

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin