next up previous notation contents
Next: 2.15.6 Redundant Decimal Expansions Up: 2.15 Real Representations Previous: 2.15.4 Continued Fractions

2.15.5 Converging Intervals

A real number r is represented by a converging sequence of rational intervals:

displaymath8945

This representation is well suited to algorithmic manipulation. All common operations are well defined using interval arithmetic, as will be demonstrated in the next chapter.

A basic number, such as tex2html_wrap_inline32525 , is provided as a computer program which produces consecutive terms of a representation of that basic number. Each term of the infinite sequence is produced after a finite number of operations is performed. Numbers can be combined by using interval arithmetic on the produced streams. It can be shown that the resulting stream also converges:

math8959

math8976

This assumes that the expression defines a real number. Some expressions, such as tex2html_wrap_inline33741 , do not define a real number. Using tex2html_wrap_inline33743 will cause delays to be introduced into the system. For example, a division will not produce output until the denominator does not contain zero. After this initial delay of d terms, one term is output for each set of input terms provided (one input term for each input stream). A system with this input-output relationship is termed an on-line arithmetic system. No delay will occur using tex2html_wrap_inline33747 , although the produced stream may begin with tex2html_wrap_inline32593 terms.

The value of any finite expression, built with the provided operators and basic numbers, can be determined to any reasonable accuracy:

math8997

The function tex2html_wrap_inline33751 is computable, as it simply computes successive terms of the representation of x until tex2html_wrap_inline33755 , and then returns k. This contrasts strongly with the previous representations. No algorithm, using a finite number of computable atomic operations, can compute: as discussed in the literature [62, 42, 12]. Note that tex2html_wrap_inline33763 does not imply tex2html_wrap_inline33765 , where x and y are two different real number representations. The remaining representations are special forms of the general converging interval representation of real numbers.


next up previous notation contents
Next: 2.15.6 Redundant Decimal Expansions Up: 2.15 Real Representations Previous: 2.15.4 Continued Fractions
Jeff TupperMarch 1996