Re: Possreps and numeric types

On Mar 25, 1:30 pm, Bob Badour <bbad..._at_pei.sympatico.ca> wrote:
> Marshall wrote:
>
> > So what if we had an internal representation for
> > integer similar to java.math.BigInteger, and an
> > internal representation for rational that was a pair
> > of integers. We can define *exact* operators for
> > these types for basic arithmetic functions.
>
> I disagree. Unless one has infinite precision, rational is
> always an approximation.

"Approximation" is perhaps not the best choice of words. We certainly have resource limits in our finite computers. There are computations that we can't do because we don't have the resources. For example, a computer might be able to add together two one billion digit integers, but not be able to add together two ten billion digit integers because it didn't have enough memory. That doesn't mean the result of adding the two one billion digit integers is approximate; on the contrary, it is precise and exact. Or consider java.util.BigInteger. Any answer you get from it will be precise, and it can handle up to four billion digit numbers. If it can't give you an answer, it'll fail in a way that can't be mistaken for an answer.

In my mind, there is a significant difference between operations that will either produce precise and exact answers or else fail, having consumed all the machine's resources, and operations that will return results that are only guaranteed up to some degree of precision.

Now admittedly the integers limited to four billion digits is not the whole of the integers, but it's a big step up from 32 bit integers. In fact, I will make a perhaps reckless claim and assert it is enough for all possible future applications. For example, supposing we might one day need a computer to operate on the number of hydrogen atoms in the universe, one hundred digits is more than enough. This leads me to suspect that one billion digits is at least ten million times more digits than anyone will ever need.

> > This differs from the cartesian/polar case, in that
> > every integer values is *exactly* representable as
> > a rational.
>
> But that doesn't change the fact that a rational is always a small
> interval in the computational model. Thus, when treated as an integer, 1
> is 1. When treated as a rational, 1 is some subrange within
> [(maxint-1)/maxint,maxint/(maxint-1)] or perhaps within
> [maxnegint/(maxnegint+1),(maxnegint+1)/maxnegint]

I don't think the model of numbers as ranges is a very good one, even for floating point. With rationals it's even less apt. If you have a rational one and a rational three and you divide, you get the exact rational one-third.

It is more useful to say that the operators, rather than the operands, are approximations. Floating point operations return approximate results in the worst case, but may return precise results in the easier cases. For example, 80 bit floating point add, subtract, and multiply on numbers with less than 32 bits of mantissa are always exact. Floating point sqrt(2) is an approximation; sqrt(4) is not.

> > It also occurs to me that an integer is a rational
> > where the denominator = 1. This starts to sound
> > like specialization by constraint.
>
> You assume one always normalizes the rational. An integer is a rational
> where the numerator modulo the denominator is always zero, which is
> trivially true when the denominator is 1.

I stand corrected.

I will say however that I would expect an implementation of rational to use normalized representation.

> > Crazier still, the fact that some rationals are integers
> > and some aren't starts to remind me of parsing a
> > string as a number. A possrep for an integer could
> > be a sequence of ascii digit characters. Then
> > constructing (selecting) an integer from a string
> > (succeeding only if the string represents an integer)
> > is isomorphic to parsing the string into a number,
> > a la parseInt or atoi or whatever. Integer isn't a
> > subset of String, but the Integer possrep sequence-
> > of-digit-chars *is* a subset of the String possrep
> > sequence-of-chars.
>
> An optional sign and a string of digits is a possible representation for
> an integer.

I stand corrected again. When can I sit down again?

> > Anyway, this post is long and confusing enough
> > for now. I think I'll go reread the relevant sections
> > of TTM now. Again. I really must buy the 3rd ed.
>
> What did you find out?

I found out that shopping used up most of the day. :-( So far I've managed to get the book off the shelf, but that's about it.

Marshall Received on Mon Mar 26 2007 - 01:03:36 CEST