Oracle FAQ Your Portal to the Oracle Knowledge Grid
HOME | ASK QUESTION | ADD INFO | SEARCH | E-MAIL US
 

Home -> Community -> Usenet -> comp.databases.theory -> Re: Possreps and numeric types

Re: Possreps and numeric types

From: Bob Badour <bbadour_at_pei.sympatico.ca>
Date: Mon, 26 Mar 2007 02:33:56 GMT
Message-ID: <oiGNh.15356$PV3.158132@ursa-nb00s0.nbnet.nb.ca>


Marshall wrote:

> 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.

Precise for integers but rationals are not integers.

> 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.

Do you prefer square root to fail having consumed all resources?

> 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.

However, that is not relevant to my point regarding rationals.

  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.

I still don't see the point in what you wrote. A billion digit integer doesn't make a whit of difference to what I wrote earlier: One still has a maximum representable integer, and a maximum representable integer defines a minimum range for the representation of each value.

>>>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.

Nevertheless, that is the best we can do. If we want to pretend something is a rational, we must acknowledge that it necessarily stands for any rational within some range regardless how large or small the range.

If you have a rational one and a rational three
> and you divide, you get the exact rational one-third.

Except that the represention of 1 actually represents a range of rational values and the representation of 3 actually represents a range of rational values before we even do the divide.

> 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.

Except that the operands themselves are approximations representing ranges. When the rational add operation adds 1 to 1, it doesn't know whether 1 is 1 or 1+epsilon/2 or 1-epsilon/5 etc. It uses the same representation for all three and for an infinite number of other rationals.

  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.

Except that 4 itself is an approximation covering the range [4-epsilon,4+epsilon] and the result of the operation represents the range [2-epsilon,2+epsilon].

>>>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.

Physical independence means allowing either without affecting the logical model. Normalization of rationals has a cost, and performance requirements may not tolerate that cost or may require it.

>>>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?

I thought I was agreeing not correcting. Were you objecting to an optional sign and a string of digits as a possible representation for an integer?

>>>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.

No biggie. Now that you have had it off the shelf for a while longer, what did you find out? Received on Sun Mar 25 2007 - 21:33:56 CDT

Original text of this message

HOME | ASK QUESTION | ADD INFO | SEARCH | E-MAIL US