Browse Prior Art Database

PROBABILISTIC ERROR ANALYSIS OF COMPUTER ARITHMETICS

IP.com Disclosure Number: IPCOM000128161D
Original Publication Date: 1979-Dec-31
Included in the Prior Art Database: 2005-Sep-15

Publishing Venue

Software Patent Institute

Related People

Erwin H. Bareiss: AUTHOR [+4]

Abstract

The problem of continuous and discrete error distribution for real computer arithmetics is discussed. The existing literature is surveyed. Several new and important theorems are proven. Results are illustrated with figures and tables.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 7% of the total text.

Page 1 of 66

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

PROBABILISTIC ERROR ANALYSIS OF COMPUTER ARITHMETICS

Erwin H. Bareiss and Jesse L. Barlow Northwestern University No. 79-11-NAM-02.

This report was prepared as an account of work sponsored by the United States Government. Neither the United States nor the United States Energy Research and Development Administration, nor any of their employees, nor any of their contractors, subcon-tractors, or their employees, makes any warranty, expressed or implied, or assumes any legal liability or responsibility for the accuracy, completeness, or usefulness of any information, appar-atus, product or process disclosed or represents that its use would not infringe privately owned rights.

December 1978 PREPARED FOR THE U.S. DEPARTMENT OF ENERGY

UNDER CONTRACT NO. EY-76-S-02-2280,

ABSTRACT

The problem of continuous and discrete error distribution for real computer arithmetics is discussed. The existing literature is surveyed. Several new and important theorems are proven. Results are illustrated with figures and tables.

CONTENTS

Introduction I

1. Deterministic Error Bounds

I., Fixed Point Arithmetic

2. Floating Point Computation 4

3. Common Floating Point Operations 5

4. Floating Point Accumulation of Sums and Inner Products 8 5. Parallel Computation 10 References 14

II. The Distribution of the Most and Least Significant Digits 15 1. The Benford Hypothesis 15 2. Multiplication and Division Reinforce the Reciprocal Distribution 19 3. The Distribution of the Intermediate and Least Significant Digits 27 References 36

III. Floating Point Arithmetic 37 1. The Ideals: Symmetric Rounding and Chopping 38 2. Guard Digits and Choice of Base 45 3. ROM Rounding 61 4. Non-Symmetric Rounding Intervals 63 References 65 IV. Fixed Point Arithmetic 66 1. The Distribution of a Constant Times a Discrete Random Variable 68 2. Fixed Point Multiplication of Two Random Numbers 74 3. Inner Product with Fixed Point Operations 82 References . The CRD Computer 88 1. Definition of the Number System 88_ 2. Geometric Error 89 3. CRD Arithmetic 91 References 95 Conclusions 96 Appendix 97

Northwestern University Page 1 Dec 31, 1979

Page 2 of 66

PROBABILISTIC ERROR ANALYSIS OF COMPUTER ARITHMETICS

List of Tables

1.1 Fixed and Floating Point Operations 13 2.1 Benford's Sample of Numbers 16 2.2 The Distance from the Reciprocal Distribution of an Extended Product as Function of the Number of Factors Selected from a uniform distribution 26 2.3 Values of Pt (a,B) for B = 2, 4, 8, 10 and 16 Reproduced from Feldstein and Goodman (1976) 31

3.1 Reproduced from Kuki and Cody (1973) (a) Binary Significance Figures for Summation Tests 500 Sums of 1024 Numbers Each 48 (b) Binary Significance Figures for 500 Products of 20 Factors 48 (c) Binary Significance Figures for Inner Produce Tests 500 Inner Products with 50 Operands 49 (d) Binary Significance Figure of Summation Tests Comparison with R:*- rounding 49

3.2 Reproduced from Cod...