You are previewing Finite Precision Number Systems and Arithmetic.
O'Reilly logo
Finite Precision Number Systems and Arithmetic

Book Description

Fundamental arithmetic operations support virtually all of the engineering, scientific, and financial computations required for practical applications, from cryptography, to financial planning, to rocket science. This comprehensive reference provides researchers with the thorough understanding of number representations that is a necessary foundation for designing efficient arithmetic algorithms. Using the elementary foundations of radix number systems as a basis for arithmetic, the authors develop and compare alternative algorithms for the fundamental operations of addition, multiplication, division, and square root with precisely defined roundings. Various finite precision number systems are investigated, with the focus on comparative analysis of practically efficient algorithms for closed arithmetic operations over these systems. Each chapter begins with an introduction to its contents and ends with bibliographic notes and an extensive bibliography. The book may also be used for graduate teaching: problems and exercises are scattered throughout the text and a solutions manual is available for instructors.

Table of Contents

  1. Cover
  2. Title
  3. Copyrights
  4. Content
  5. Preface
  6. 1. Radix polynomial representation
    1. 1.1 Introduction
    2. 1.2 Radix polynomials
    3. 1.3 Radix-β numbers
    4. 1.4 Digit symbols and digit strings
    5. 1.5 Digit sets for radix representation
    6. 1.6 Determining a radix representation
    7. 1.7 Classifying base-digit set combinations
    8. 1.8 Finite-precision and complement representations
      1. 1.8.1 Finite-precision radix-complement representations
    9. 1.9 Radix-β approximation and roundings
      1. 1.9.1 Best radix-β approximations
      2. 1.9.2 Rounding into finite representations
    10. 1.10 Other weighted systems
      1. 1.10.1 Mixed-radix systems
      2. 1.10.2 Two-level radix systems
      3. 1.10.3 Double-radix systems
    11. 1.11 Notes on the literature
  7. 2. Base and digit set conversion
    1. 2.1 Introduction
    2. 2.2 Base/radix conversion
    3. 2.3 Conversion into non-redundant digit sets
    4. 2.4 Digit set conversion for redundant systems
      1. 2.4.1 Limited carry propagation
      2. 2.4.2 Carry determined by the right context
      3. 2.4.3 Conversion into a contiguous digit set
      4. 2.4.4 Conversion into canonical, non-adjacent form
    5. 2.5 Implementing base and digit set conversions
      1. 2.5.1 Implementation in logic
      2. 2.5.2 On-line digit set conversion
    6. 2.6 The additive inverse
    7. 2.7 Notes on the literature
  8. 3. Addition
    1. 3.1 Introduction
    2. 3.2 How fast can we compute?
    3. 3.3 Digit addition
    4. 3.4 Addition with redundant digit sets
    5. 3.5 Basic linear-time adders
      1. 3.5.1 Digit serial and on-line addition
    6. 3.6 Sub-linear time adders
      1. 3.6.1 Carry-skip adders
      2. 3.6.2 Carry-select adders
      3. 3.6.3 Carry-look-ahead adders
    7. 3.7 Constant-time adders
      1. 3.7.1 Carry-save addition
      2. 3.7.2 Borrow-save addition
    8. 3.8 Addition and overflow in finite precision systems
      1. 3.8.1 Addition in redundant digit sets
      2. 3.8.2 Addition in radix-complement systems
      3. 3.8.3 1’s complement addition
      4. 3.8.4 2’s complement carry-save addition
    9. 3.9 Subtraction and sign-magnitude addition
      1. 3.9.1 Sign-magnitude addition and subtraction
      2. 3.9.2 Bit-serial subtraction
    10. 3.10 Comparisons
      1. 3.10.1 Equality testing
      2. 3.10.2 Ordering relations
      3. 3.10.3 Leading zeroes determination
    11. 3.11 Notes on the literature
  9. 4. Multiplication
    1. 4.1 Introduction
    2. 4.2 Classification of multipliers
    3. 4.3 Recoding and partial product generation
      1. 4.3.1 Radix-2 multiplication
      2. 4.3.2 Radix-4 multiplication
      3. 4.3.3 High-radix multiplication
    4. 4.4 Sign-magnitude and radix-complement multiplication
      1. 4.4.1 Mapping into unsigned operands
      2. 4.4.2 2’s complement operands
      3. 4.4.3 The Baugh and Wooley scheme
      4. 4.4.4 Using a recoded multiplier
    5. 4.5 Linear-time multipliers
      1. 4.5.1 The classical iterative multiplier
      2. 4.5.2 Array multipliers
      3. 4.5.3 LSB-first serial/parallel multipliers
      4. 4.5.4 A pipelined serial/parallel multiplier
      5. 4.5.5 Least-significant bit first (LSB-first) serial/serial multipliers
      6. 4.5.6 On-line or most-significant bit first (MSB-first) multipliers
    6. 4.6 Logarithmic-time multiplication
      1. 4.6.1 Integer multipliers with overflow detection
    7. 4.7 Squaring
      1. 4.7.1 Radix-2 squaring
      2. 4.7.2 Recoded radix-4 squaring
      3. 4.7.3 Radix-4 squaring by operand dual recoding
    8. 4.8 Notes on the literature
  10. 5. Division
    1. 5.1 Introduction
    2. 5.2 Survey of division and reciprocal algorithms
      1. 5.2.1 Digit-serial algorithms
      2. 5.2.2 Iterative refinement algorithms
      3. 5.2.3 Resource requirements
      4. 5.2.4 Reciprocal look-up algorithms
    3. 5.3 Quotients and remainders
      1. 5.3.1 Integer quotient, remainder pairs
      2. 5.3.2 Radix-β quotient, remainder pairs
      3. 5.3.3 Converting between radix-β quotient, remainder pairs
    4. 5.4 Deterministic digit-serial division
      1. 5.4.1 Restoring division
      2. 5.4.2 Robertson diagrams
      3. 5.4.3 Non-restoring division
      4. 5.4.4 Binary SRT division
    5. 5.5 SRT division
      1. 5.5.1 Fundamentals of SRT division
      2. 5.5.2 Digit selection
      3. 5.5.3 Exploiting symmetries
      4. 5.5.4 Digit selection by direct comparison
      5. 5.5.5 Digit selection by table look-up
      6. 5.5.6 Architectures for SRT division
    6. 5.6 Multiplicative high-radix division
      1. 5.6.1 Short reciprocal division
      2. 5.6.2 Prescaled division
      3. 5.6.3 Prescaled division with remainder
      4. 5.6.4 Efficiency of multiplicative high radix division
    7. 5.7 Multiplicative iterative refinement division
      1. 5.7.1 Newton–Raphson division
      2. 5.7.2 Convergence division
      3. 5.7.3 Postscaled division
      4. 5.7.4 Efficiency of iterative refinement division
    8. 5.8 Table look-up support for reciprocals
      1. 5.8.1 Direct table look-up
      2. 5.8.2 Ulp accurate and monotonic reciprocal approximations
      3. 5.8.3 Bipartite tables
      4. 5.8.4 Linear and quadratic interpolation
    9. 5.9 Notes on the literature
  11. 6. Square root
    1. 6.1 Introduction
    2. 6.2 Roots and remainders
    3. 6.3 Digit-serial square root
      1. 6.3.1 Restoring and non-restoring square root
      2. 6.3.2 SRT square root
      3. 6.3.3 Combining SRT square root with division
    4. 6.4 Multiplicative high-radix square root
      1. 6.4.1 Short reciprocal square root
      2. 6.4.2 Prescaled square root
    5. 6.5 Iterative refinement square root
      1. 6.5.1 Newton–Raphson square root
      2. 6.5.2 Newton–Raphson root-reciprocal
      3. 6.5.3 Convergence square root
      4. 6.5.4 Exact and directed one-ulp roots
    6. 6.6 Notes on the literature
  12. 7. Floating-point number systems
    1. 7.1 Introduction
    2. 7.2 Floating-point factorization and normalization
      1. 7.2.1 Floating-point number factorization
      2. 7.2.2 Finite precision floating-point number systems
      3. 7.2.3 Distribution of finite precision floating-point numbers
      4. 7.2.4 Floating-point base conversion and equivalent digits
    3. 7.3 Floating-point roundings
      1. 7.3.1 Precise roundings
      2. 7.3.2 One-ulp roundings and tails
      3. 7.3.3 Inverses of the rounding mappings
    4. 7.4 Rounded binary sum and product implementation
      1. 7.4.1 Determining quasi-normalized rounding intervals
      2. 7.4.2 Rounding from quasi-normalized rounding intervals
      3. 7.4.3 Implementing floating-point addition and subtraction
    5. 7.5 Quotient and square root rounding
      1. 7.5.1 Prenormalizing rounded quotients and roots
      2. 7.5.2 Quotient rounding using remainder sign
      3. 7.5.3 Rounding equivalence of extra accurate quotients
      4. 7.5.4 Precisely rounded division in Qpβ
      5. 7.5.5 Precisely rounded square root
      6. 7.5.6 On-the-fly rounding
    6. 7.6 The IEEE standard for floating-point systems
      1. 7.6.1 Precision and range
      2. 7.6.2 Operations on floating-point numbers
      3. 7.6.3 Closure
      4. 7.6.4 Floating-point encodings
    7. 7.7 Notes on the literature
  13. 8. Modular arithmetic and residue number systems
    1. 8.1 Introduction
    2. 8.2 Single-modulus integer systems and arithmetic
      1. 8.2.1 Determining the residue |a|m
      2. 8.2.2 The multiplicative inverse
      3. 8.2.3 Implementation of modular addition and multiplication
      4. 8.2.4 Multioperand modular addition
      5. 8.2.5 ROM-based addition and multiplication
      6. 8.2.6 Modular multiplication for very large moduli
      7. 8.2.7 Modular exponentiation
      8. 8.2.8 Inheritance and periodicity modulo 2k
    3. 8.3 Multiple modulus (residue) number systems
    4. 8.4 Mappings between residue and radix systems
    5. 8.5 Base extensions and scaling
      1. 8.5.1 Mixed-radix base extension
      2. 8.5.2 CRT base extension
      3. 8.5.3 Scaling
    6. 8.6 Sign and overflow detection, division
      1. 8.6.1 Overflow
      2. 8.6.2 Sign determination and comparison
      3. 8.6.3 The core function
      4. 8.6.4 General division
    7. 8.7 Single-modulus rational systems
    8. 8.8 Multiple-modulus rational systems
    9. 8.9 p-adic expansions and Hensel codes
      1. 8.9.1 p-adic numbers
      2. 8.9.2 Hensel codes
    10. 8.10 Notes on the literature
  14. 9. Rational arithmetic
    1. 9.1 Introduction
    2. 9.2 Numerator–denominator representation systems
    3. 9.3 The mediant rounding
    4. 9.4 Arithmetic on fixed- and floating-slash operands
    5. 9.5 A binary representation of the rationals based on continued fractions
    6. 9.6 Gosper’s Algorithm
    7. 9.7 Bit-serial arithmetic on rational operands
    8. 9.8 The RPQ cell and its operation
    9. 9.9 Notes on the literature
  15. Author index
  16. Index