Re: Possreps and numeric types
Date: Mon, 26 Mar 2007 21:40:41 GMT
Message-ID: <t5XNh.15601$PV3.159796_at_ursa-nb00s0.nbnet.nb.ca>
Marshall wrote:
> On Mar 25, 6:33 pm, Bob Badour <bbad..._at_pei.sympatico.ca> wrote:
>
>>Marshall wrote: >> >> >>>"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.
>
> The situation for rationals and integers is the same;
> one is just a pair of the other. The result of a rational
> multiply is either 1) the exactly right answer or 2) failure
> due to exceeding resource limits.
I disagree. In a finite computer, a rational necessarily represents a range of rational values as already explained.
Consider the following, assuming Rational(numerator,denominator).
x = Rational(maxint,(maxint-1)) + Rational((maxint-1),maxint)
You are suggesting that adding two numbers approximately equal to 1 should result in an error for exceeding resource limits instead of a number approximately equal to 2 and perhaps represented as 2.
The integer maxint above need not be fixed by the language and could be determined by available memory. Regardless, such a maximum integer exists in any finite computer.
Do you consider "~1+~1 = error" an acceptable limitation?
>>>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?
>
> The question is a good one however it does not address
> the distinction I am trying to make between precise and
> approximate operations. To answer your question, I would
> treat square root as an approximate operation. (The usual
> floating point implementation.)
No distinction exists when we start with approximate representations. We cannot represent the rationals in finite computers. The best we can do is approximate representing them.
> A common way of viewing the situation today is that we
> have some exact numbers and some inexact numbers.
> I am arguing that there are advantages to a different model,
> in which all numbers are exact, and some *operations* are
> exact and some are approximate.
I suggest intellectual honesty requires us to admit that one cannot represent infinite precision in finite space. Thus, some of our numbers are inexact regardless.
>>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,
>
> I agree.
>
>
>>and a maximum representable integer >>defines a minimum range for the representation of each value.
>
> I disagree.
How do you represent:
(Rational(maxint,(maxint-1)) + Rational(1,1)) / Rational(2, 1)
?
ie. the midpoint between 1+epsilon and 1.
Do you consider "(~1+~1)/~2 = error" an acceptable limitation?
>>>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.
>
> I don't see how that follows. I don't see the "necessarily" part.
Finite computers have a finite number of states for representing different values. Thus, we cannot represent the set of rationals. The best we can do is represent an approximation of them.
>>>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.
>
> Same objection.
Same explanation.
>>>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.
>
> Same objection again.
Same explanation again.
>>>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].
>
> Same objection again. Can you say *why* you think this is
> necessarily true?
I already did several messages ago. With finite computers, the best we can do is pretend to represent rationals; we cannot actually represent them. Given finite computers, the best we can do is represent an approximation of rationals.
In a finite computer, the representation of a rational value that represents 1 necessarily represents some range within [(maxint-1)/maxint,maxint/(maxint-1)] comprising an infinite set of rational values. We ignore that at our peril.
>>>>>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?
>
> Ah, I just overreacted. I left off the part about the sign; your
> statement
> of the situation was more complete and accurate.
>
>
>>>>>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?
>
> Bleah, I barely got ten pages done. Lots of distractions. Probably
> won't attempt it today, what with the hangover and all. Tomorrow
> while the kids are at school is more promising. I haven't looked at
> SbyC in a long time; especially wanna reread that part, but not
> until I've reread the possreps stuff.
Try to keep in mind that computers are finite artifacts. As long as they remain so, we will have to contend with largest representable numbers and smallest representable differences. Received on Mon Mar 26 2007 - 23:40:41 CEST