edwards@houxa.UUCP (D.LEWAN) (02/06/86)
I am currently considering the real numbers, some of their
constructive aspects and specific uses, and different
encodings for them for digital computers. This article is a
request for encodings that may not be well known as well
(but are indeed useful), as particular uses for those
encodings. Such a use is probably one for which
1. that encoding is convenient and
2. another encoding would be difficult to use.
A few philosophical notes should be made before I go too
far.
The act of encoding is that of assigning, to a *meaningful*
object, a name from which the object (or its meaning,
anyway) can be recreated. For example, to the object
"fifteen" we may assign the name "15". Now, from "15" we
can reconstruct "fifteen" by interpreting it as "10 + 5",
and the objects named by "10", "+" and "5" are all well
defined and understood. I cannot name all the real numbers
since there are only a countable number of names available,
and there are an uncountable number of reals. But I can
select subsets of the reals tailored to my particular needs
and for some of those subsets I can find worthwhile
encodings.
The standard exponent/base approach to real number
representation is a style that in some sense has the best
and worst of all worlds. Its precision is generally good
enough for most arithmetic applications, but absolute
precision waxes for large numbers, where the type integer
might in fact be more precise. It also doesn't guarantee,
for example, that n-th roots, when raised to the n-th power,
yield the original numbers, i.e. that
n ---- n
\/ q = q
in all cases. (Imagine moving your PC's best approximation
of the square root of 2 to a CRAY II and then performing
arithmetic.)
There are representations that do preserve such algebraic
properties, unfortunately they lose meaningful precision.
If one only knows that the square of a certain number always
yields 2 one does not necessarily know if it is greater than
or less than 0. (High school math conventions do no good
here.)
Now, I know that preservation of algebraic properties is
just one of many that might be of interest to a particular
application.
I am sending this plea to the net to find a wealth of
applications that might run better with less well known
encodings for specific real numbers.
Great thanks go to anyone who can help out.
Doug
(...!ihnp4!houxa!edwards)mac@uvacs.UUCP (Alex Colvin) (02/11/86)
> request for encodings that may not be well known as well
Continued fractions are a number system without unique representation,
allowing arithmetic to be pipelined digit by digit. Results can be
computed to the required precision.
There is a description of this by R. W. Gosper in MIT AI memo 239,
item#101. He refers to Knuth, V. 2, p. 316.