Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

RESIDUE OR MODULAR ARITHMETIC

IP.com Disclosure Number: IPCOM000128693D
Original Publication Date: 1978-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 25 page(s) / 57K

Publishing Venue

Software Patent Institute

Related People

R.T. Gregory: AUTHOR [+4]

Abstract

Since an automatic digital computer is a finite machine it is capable of representing, internally, only a finite set of numbers. Thus, any attempt to use an automatic digital computer to do arithmetic in the field of real numbers (11,+,-) is doomed to failure because R is an infinite set and most of the elements in this set cannot be represented in a computer. This does not mean, however, that we do not attempt to approximate the arithmetic of (R,+,-) on a computer. We often attempt this approximation by using the so-called floating-point numbers, F , more appropriately called the set of computer-representable numbers. The set F is a set of real numbers with the following properties: (a) F is a finite subset of the rational numbers. (b) F is symmetric with respect to the origin and there are usually two computer representations of zero. (c) The elements of IF are not evenly distributed along the real line. The interval between two "adjacent" computer-representable numbers is quite small near the origin and becomes increasingly large as one moves away from the origin. In the vicinity of the largest possible computer-representable number the interval is quite large. For example, see Forsythe, Malcolm, and Moler [1977] ) page 12. (d) Almost all of the "familiar" rational numbers are excluded from F For example, on a binary computer the only candidates for membership in F are rational numbers of the form p/q , where q is a

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

Page 1 of 25

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

RESIDUE OR MODULAR ARITHMETIC

R.T. Gregory E.V. Krishnamurthy

CS-78-28 June 1978

1. Introduction

Since an automatic digital computer is a finite machine it is capable of representing, internally, only a finite set of numbers. Thus, any attempt to use an automatic digital computer to do arithmetic in the field of real numbers (11,+,-) is doomed to failure because R is an infinite set and most of the elements in this set cannot be represented in a computer. This does not mean, however, that we do not attempt to approximate the arithmetic of (R,+,-) on a computer. We often attempt this approximation by using the so-called floating-point numbers, F , more appropriately called the set of computer-representable numbers. The set F is a set of real numbers with the following properties:

(a) F is a finite subset of the rational numbers.

(b) F is symmetric with respect to the origin and there are usually two computer representations of zero.

(c) The elements of IF are not evenly distributed along the real line. The interval between two "adjacent" computer-representable numbers is quite small near the origin and becomes increasingly large as one moves away from the origin. In the vicinity of the largest possible computer-representable number the interval is quite large. For example, see Forsythe, Malcolm, and Moler [1977] ) page 12.

(d) Almost all of the "familiar" rational numbers are excluded from F For example, on a binary computer the only candidates for membership in F are rational numbers of the form p/q , where q is a power of two. Thus, such numbers as 1/10, 1/3, 5/6 and 2/7 are excluded.

(e) The system (F,+,,) does not constitute a field (primarily because we do not have closure under either of the two binary operations indicated).

Thus, there is no possibility of representing the continuum of real numbers in any detail. A "practical" solution to this problem, in many cases, is to represent a real number x by its closest computer-representable number x., thereby introducing the rounding error

(1.1)

(Equation Omitted)

Because of the lack of closure, rounding errors are also introduced as a result of arithmetic operations on elements of F For example, if x and y are two "adjacent" elements in F , then

(1.2)

University of Tennessee Page 1 Dec 31, 1978

Page 2 of 25

RESIDUE OR MODULAR ARITHMETIC

(Equation Omitted)

is not an element of F and will have to be represented by z , the element in F nearest to z In this example, ~z could be either -x or y

To some people, the effect of inexact arithmetic (and of rounding errors) may not appear to be too serious. However, it is well known that, from the point of view of backward error analysis (see Young and Gregory [19721, P. 10, for example), the computed solutiont to a problem can be interpreted as the exact solution to a slightly perturbed problem. Furthermore, there exists a class of problems, called ill-conditioned problems for...