Computer-hardware Evaluation Of Mathematical Functions

by Amos R Omondi

Overview

Computer-Hardware Evaluation of Mathematical Functions provides a thorough up-to-date understanding of the methods used in computer hardware for the evaluation of mathematical functions: reciprocals, square-roots, exponentials, logarithms, trigonometric functions, hyperbolic functions, etc. It discusses how the methods are derived, how they work, and how well they work. The methods are divided into four core themes: CORDIC, normalization, table look-up, and polynomial approximations. In each case, the author carefully considers the mathematical derivation and basis of the relevant methods, how effective they are (including mathematical errors analysis), and how they can be implemented in hardware.This book is an excellent resource for any student or researcher seeking a comprehensive, yet easily understandable, explanation of how computer chips evaluate mathematical functions.

Product Details

ISBN-13:	9781783268603
Publisher:	Imperial College Press
Publication date:	12/14/2015
Pages:	432
Product dimensions:	6.30(w) x 9.20(h) x 1.10(d)

Table of Contents

Preface vii

Acknowledgments xiii

1 Errors, Range Reduction, and Rounding 1

1.1 Errors 2

1.1.1 Computation errors 5

1.1.2 Propagated errors 7

1.1.3 Iterative algorithms 10

1.2 Range reduction 11

1.3 Rounding 18

2 Redundant Representations and High-Speed Arithmetic 21

2.1 Redundant number representations 23

2.1.1 Carry-save representation 24

2.1.2 Redundant signed-digit representation 26

2.2 High-speed multiplication 35

2.2.1 Multiplier recoding 35

2.2.2 Squaring 42

2.3 High-speed division 43

2.3.1 Multiplicative normalization 44

2.3.2 Additive normalization 62

2.3.3 SRT 69

2.3.4 Very high radix 89

3 Cordic 93

3.1 Trigonometric functions 94

3.2 Inverse trigonometric functions 106

3.3 Hyperbolic functions and inverses 113

3.4 Linear functions 120

3.5 Errors and datapath precision 124

3.6 Implementation 126

4 High-Performance CORDIC 131

4.1 De Lugish CORDIC 132

4.2 Correcting-Rotations CORDIC 137

4.3 Branching CORDIC 139

4.4 Differential CORDIC 143

4.5 Double-Rotations CORDIC 147

4.6 High-radix CORDIC 151

4.7 Very-high-radix CORDIC 162

5 Normalization Algorithms 167

5.1 Normalization constants 169

5.2 Reciprocals 171

5.3 Exponential and logarithm functions 174

5.3.1 Exponential 175

5.3.2 Logarithm 180

5.4 Trigonometric functions and inverses 184

5.5 Square root and inverse 187

5.6 High-performance exponential and logarithm 194

5.6.1 Early termination and zero skipping 194

5.6.2 Redundant representation and high radix 200

5.6.3 Very-high-radix computation 215

6 Polynomial and Rational-Function Approximations 223

6.1 Quality of approximation 224

6.2 Taylor series 227

6.3 Chebyshev polynomials 236

6.4 Legendrc polynomials 246

6.5 Interpolation 247

6.6 Rational functions 254

7 Table Lookup and Segmented Polynomial Approximations 261

7.1 Polynomial-based table lookup 264

7.1.1 Bipartite tables 265

7.1.2 Multipartite tables 271

7.1.3 Addition-Table lookup-Addition 285

7.2 Table-driven polynomial approximation 295

7.3 Segmented polynomial approximation 300

7.3.1 Uniform segmentation 301

7.3.2 Segment boundaries and numbers 308

7.3.3 Hierarchical segmentation 310

7.3.4 LUT cascades 315

7.3.5 Address remapping 317

7.3.6 Errors 321

8 Reciprocals, Square Roots, and Inverse Square Roots 329

8.1 Polynomial approximations 330

8.2 Reciprocals 334

8.2.1 Newton-Raphson method 334

8.2.2 Goldschmidt normalization 342

8.3 Square root and inverse 349

8.3.1 Newton-Raphson method and variations 349

8.3.2 Goldschmidt normalization 356

8.3.3 Multiplicative normalization: non-redundant digit set 359

8.3.4 Multiplicative normalization: redundant digit set 362

8.3.5 Additive normalization: redundant digit set 369

8.3.6 "SRT" algorithms 377

8.3.7 High-radix computation 389

References 397

Index 411