Re: Possreps and numeric types

Marshall wrote:

> This is more of me trying to sort out my confusion about possreps.
>
> Lately I have been thinking about numeric types. I find the
> situation tremendously annoying. On the one hand, one
> sorely wants to faithfully model as many of the algebraic
> properties of numbers as possible. On the other hand,
> the real numbers are only available as an approximation,
> floating point numbers, and operations on these
> approximations do *not* possess the vast majority of
> these algebraic properties. Harumph.
>
> I read a paper recently that was an analysis of the situation
> in the Scheme programming language. Scheme made some
> ambitious forays into the so called "Numeric Tower" or
> the hierarchy of natural, integer, rational, etc.
>
> http://repository.readscheme.org/ftp/papers/sw2004/egner.pdf
>
> The paper had some recommendations as to how to do
> it better still. I found the paper quite convincing.
>
> In the past I've been quite unhappy with the canonical
> example of possreps, which seems to be the pair
> (cartesian, polar) for some type, sometimes Point, or
> Bob has suggested Complex. It disturbs me that
> a cartesian (1,1) is not a value that can be represented
> in polar coordinates in a computer, because the radius
> is sqrt(1^2+1^2) = sqrt(2) = a transcendental number.
> Since transcendentals have an infinite number of
> nonrepeating digits (think pi) they are not representable
> as a digit sequence in base 2, base 10, or otherwise.
> (There are other ways of representing numbers,
> as the solutions to equations, but these are quite
> complicated and have their own problems.)
>
> Anyway, a vague idea I have is something related to
> representation of numbers. Let us consider just the
> case of the rationals and the integers. Every integer
> is a rational. The rationals have all the popular and
> attractive algebraic properties we are so used to
> seeing featured in Us magazine and Entertainment
> Weekly. Therefore all those same properties apply
> to the integers. (Note I am not speaking of 32 bit
> integers.)
>
> 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.

  (But
> not for trigonometric functions, logs, and roots.)
> The implementation of these operators for integer
> is likely to be significantly faster than the ones
> for rational. This starts to sound like possreps to
> me. (Although I don't think of possreps as being
> used with subsets.)
>
> 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]

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

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

> Wacky wacky.

What is so wacky about it?

> 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? Received on Sun Mar 25 2007 - 23:30:57 CEST