time complexity

[Dik T. Winter]

> On Wed, 24 Oct 2007 00:58:16 GMT, "Dik T. Winter"

>
> Well, no, it is not.
>
>
> No, they aren't the real values - they are representations of the
> real values.

So 'sqrt(2)' expresses the real number, and there are lots of computers
where I can express it that way. 'sqrt(2)' is not different from '123'
in that aspect, both give rules on how to calculate the actual number
if there is any need.

 

[Ben Bacarisse]

I agree with Dik. The 'representations' are attempts to express
those values with some combination of digits and numerical base,
which can never be exact, since the values are transcendental.

That's a leap! Neither of the number you quote are transcendental
although the number that is at the heart of this thread may well be.

 

[CBFalconer]

That's a leap! Neither of the number you quote are transcendental
although the number that is at the heart of this thread may well be.

Are you claiming sqrt(2) is not transcendental? It is a long time
since I took math classes, and I have been operating under the
(possibly delusional) assumption that a number that cannot be
expressed exactly is transcendental. According to that any
non-rational value is transcendental. Maybe it has to depend on
the series expansion of the value.

 

[Richard Harter]

So 'sqrt(2)' expresses the real number, and there are lots of computers
where I can express it that way. 'sqrt(2)' is not different from '123'
in that aspect, both give rules on how to calculate the actual number
if there is any need.

Just so. Or more precisely, to calculate the "actual number" to
any desired precision as desired. Let us walk around that large
pool of quicksand labelled "what is a number" and focus on usage.

In practice a real number is any point on the real line; a
canonical representation is in the form of an infinite sequence
of digits in any convenient base. The original point I thought
you were making is that real numbers cannot in general be
represented on computers; that's why we use things like floating
point. I expect that we are both on the same page here. Perhaps
we should make a bow to the gods of topicality and leave it at
that.


Richard Harter, (e-mail address removed)
http://home.tiac.net/~cri, http://www.varinoma.com
In the fields of Hell where the grass grows high
Are the graves of dreams allowed to die

 

[pete]

CBFalconer wrote:

Are you claiming sqrt(2) is not transcendental?

The square root of two is irrational.
Transcendental numbers are also not the roots of any equation.
pi is transcendental.

 

[Richard Heathfield]

CBFalconer said:

Are you claiming sqrt(2) is not transcendental?

Yes.

A transcendental number is one that is not a root of any integer polynomial
equation.

sqrt(2) is a root of the equation: x^2 - 2 = 0

Therefore, sqrt(2) is not transcendental, QED.

It is a long time
since I took math classes, and I have been operating under the
(possibly delusional) assumption that a number that cannot be
expressed exactly is transcendental.

The word for which you are reaching is "irrational". It is indeed the case
that sqrt(2) is irrational.

 

[Richard Heathfield]

pete said:

The square root of two is irrational.
Transcendental numbers are also not the roots of any equation.

Close, but no banana.

pi is transcendental.

It is the root of the equation x - pi = 0. Therefore, according to your
definition of "transcendental", pi is *not* transcendental. Nevertheless,
we know that it /is/. Therefore, your definition must be wrong.

 

[user923005]

The square root of two is irrational.
Transcendental numbers are also not the roots of any equation.
pi is transcendental.

A transcendental number is not the root of any integer polynomial.
There are equations which have pi as root(s).

 

[CBFalconer]

CBFalconer said:



Yes.

A transcendental number is one that is not a root of any integer
polynomial equation.

sqrt(2) is a root of the equation: x^2 - 2 = 0

Therefore, sqrt(2) is not transcendental, QED.


The word for which you are reaching is "irrational". It is indeed
the case that sqrt(2) is irrational.

No, I wasn't reaching for 'irrational'. I was misusing
'transcendental'. I had entirely forgotton about roots of integer
polynomial equations.

 

[Dik T. Winter]

> On Wed, 24 Oct 2007 10:53:07 GMT, "Dik T. Winter"
....
> In practice a real number is any point on the real line; a
> canonical representation is in the form of an infinite sequence
> of digits in any convenient base.

Some practice. Much of what I have done would have given wrong results
if (for instance) sqrt(2) had been given as a finite approximation.

 

[Ben Bacarisse]

Are you claiming sqrt(2) is not transcendental?

Done to death now but yes. Though "irrational" is often used for
numbers like sqrt(2) the term in not very helpful since transcendental
numbers are also irrational. The modern term is "algebraic" giving
the hierarchy:

naturals + integers + rational + algebraics + transcendentals = reals

(with each class including those to the right).

 

[Philip Potter]

Done to death now but yes. Though "irrational" is often used for
numbers like sqrt(2) the term in not very helpful since transcendental
numbers are also irrational. The modern term is "algebraic" giving
the hierarchy:

naturals + integers + rational + algebraics + transcendentals = reals

(with each class including those to the right).

Not the way I see it. Using < for the subset-of relation, we have:

Naturals < integers < rationals < algebraics

But it is certainly not the case that algebraics < trancendentals! In fact

algebraics I trancendentals = 0

where I is intersection and 0 is the empty set.

Phil

 

[CBFalconer]

Not the way I see it. Using < for the subset-of relation, we have:

Naturals < integers < rationals < algebraics

But it is certainly not the case that algebraics < trancendentals!
In fact

algebraics I trancendentals = 0

where I is intersection and 0 is the empty set.

I vaguely remember a proof that between any two rationals we can
find an infinity of transcendentals. Also that rationals are
countable (1 to 1 correspondence with integers), while
transcendentals are not. This leads to the various classes of
infinity. The details are all lost to bit rot.

 

[Philip Potter]

I vaguely remember a proof that between any two rationals we can
find an infinity of transcendentals. Also that rationals are
countable (1 to 1 correspondence with integers), while
transcendentals are not. This leads to the various classes of
infinity. The details are all lost to bit rot.

We're getting highly OT here, but between any two rationals lie an
infinity of rationals. But it's a smaller infinity than the infinity of
trancendentals.

Rationals are countable because they can be expressed as a pair of
integers (numerator, denominator) and the set of pairs of integers forms
a bijection with the set of integers (proof omitted here).

Trancendentals are uncountable due to cantor's diagonal argument.

Phil

 

[Richard Tobin]

I vaguely remember a proof that between any two rationals we can
find an infinity of transcendentals. Also that rationals are
countable (1 to 1 correspondence with integers), while
transcendentals are not. This leads to the various classes of
infinity. The details are all lost to bit rot.

The algebraic numbers are also countable, since there are only a
countable number of polynomials with integer coefficients, and each
has only a finite number of roots. Since the transcendentals are the reals
excluding the algebraics, the transcendentals must be uncountable.

Furthermore, since there are only countably many algebraics, *any*
uncountable set of reals must contain uncountably many
transcendentals.

It's then obvious that there are uncountably many transcendentals
between any two distinct reals, since any non-empty interval contains
uncountably many reals.

-- Richard

 

[Ben Bacarisse]

Not the way I see it. Using < for the subset-of relation, we have:

Naturals < integers < rationals < algebraics

But it is certainly not the case that algebraics < trancendentals! In fact

algebraics I trancendentals = 0

where I is intersection and 0 is the empty set.

Yes, of course. The trancendentals are defined to not include any of
the "simpler" sets.

 

[Ben Bacarisse]

We're getting highly OT here,
snap!

Rationals are countable

as are the algebraic numbers (as I am sure you know). Un-countability
only come with chucking in the "rest"!

 

[Ed Prochak]

We're getting highly OT here, but between any two rationals lie an
infinity of rationals. But it's a smaller infinity than the infinity of
trancendentals.

Rationals are countable because they can be expressed as a pair of
integers (numerator, denominator) and the set of pairs of integers forms
a bijection with the set of integers (proof omitted here).

Trancendentals are uncountable due to cantor's diagonal argument.

Phil

OKAY lets make it topical. I came up with this algorithm to solve a
problem in Oracle PLSQL (which only has one dimensional arrays), but
it can be useful in C also.

To make it more relevant to C let me set the stage.

You need an extensible 2D array. You can simulate this with a linear
array and this routine.

/**************
For a linear array X[]
Given 2 indices A,B
return an index value that maps to a location in X[]
With first element at (0,0) and X[] is zero based.
*********************************************/
int twod( a, b )
{
int k,n,ndx;
k=a+b+1;
n=k*(k+1);
n=n/2;
ndx = n-b-1; /* make zero based for C */
return ndx;
}



and the caller uses this within the array, like

X[twod(3,5)]++ ;

/* and for extensible array situations, check the index first */
if ( twod(aa,bb) >numelementsin(X) )
{
/* need to reallocate to have room for the next entry */
<realloc code>
/* wouldn't need this in Oracle, which has sparse arrays */
/* and allocates elements for you */
}
X[twod(aa,bb)]=nextvalue;

A final comment:
this routine basically fills the array along diagonals. So it really
is best if your application needs a triangular array rather than a
square one. For example if you want to be able to use X[twod(10,10)],
then X must have 221 elements.

Enjoy.
Ed

 

[pete]

A transcendental number is not the root of any integer polynomial.
There are equations which have pi as root(s).

Thank you.

 

[Charles Richmond]

I vaguely remember a proof that between any two rationals we can
find an infinity of transcendentals. Also that rationals are
countable (1 to 1 correspondence with integers), while
transcendentals are not. This leads to the various classes of
infinity. The details are all lost to bit rot.

Countable and uncountable infinity are ideas put forth
by Georg Cantor. Cantor spent a lot of time in mental
institutions. I do *not* think these two facts are
unrelated...