Velocity Reviews > time complexity

# time complexity

Ben Bacarisse
Guest
Posts: n/a

 10-25-2007
CBFalconer <(E-Mail Removed)> writes:

> Ben Bacarisse wrote:
>> CBFalconer <(E-Mail Removed)> writes:

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

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

--
Ben.

Philip Potter
Guest
Posts: n/a

 10-25-2007
Ben Bacarisse wrote:
> 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
Guest
Posts: n/a

 10-25-2007
Philip Potter wrote:
> Ben Bacarisse wrote:
>
>> 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.

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.

--
Chuck F (cbfalconer at maineline dot net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net>

--
Posted via a free Usenet account from http://www.teranews.com

Philip Potter
Guest
Posts: n/a

 10-25-2007
CBFalconer wrote:
> Philip Potter wrote:
>> 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.

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
Guest
Posts: n/a

 10-25-2007
In article <(E-Mail Removed)>,
CBFalconer <(E-Mail Removed)> wrote:

>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
--
"Consideration shall be given to the need for as many as 32 characters
in some alphabets" - X3.4, 1963.

Ben Bacarisse
Guest
Posts: n/a

 10-25-2007
Philip Potter <(E-Mail Removed)> writes:

> Ben Bacarisse wrote:
>> 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.

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

--
Ben.

Ben Bacarisse
Guest
Posts: n/a

 10-25-2007
Philip Potter <(E-Mail Removed)> writes:

> CBFalconer wrote:
>> Philip Potter wrote:
>>> 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.

>
> 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"!

--
Ben.

Ed Prochak
Guest
Posts: n/a

 10-25-2007
On Oct 25, 10:59 am, Philip Potter <(E-Mail Removed)> wrote:
> CBFalconer wrote:
> > Philip Potter wrote:
> >> 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.

>
> 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
Guest
Posts: n/a

 10-25-2007
user923005 wrote:
>
> On Oct 24, 5:03 pm, pete <(E-Mail Removed)> wrote:
> > 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.

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

Thank you.

--
pete

Charles Richmond
Guest
Posts: n/a

 10-28-2007
CBFalconer wrote:
> Philip Potter wrote:
>> Ben Bacarisse wrote:
>>
>>> 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.

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

--
+----------------------------------------------------------------+
| Charles and Francis Richmond richmond at plano dot net |
+----------------------------------------------------------------+