# time complexity

Discussion in 'C Programming' started by ashu, Oct 18, 2007.

1. ### ashuGuest

there is question :
What is the smallest value of n such that an algorithm whose running
time is 100n2 runs faster than an algorithm whose running time is 2n
on the same machine.

i can`t understand this question plz help me

ashu, Oct 18, 2007

2. ### Keith ThompsonGuest

ashu <> writes:
> there is question :
> What is the smallest value of n such that an algorithm whose running
> time is 100n2 runs faster than an algorithm whose running time is 2n
> on the same machine.
>
> i can`t understand this question plz help me

In any case, this isn't a question about the C programming language,
so I don't know why you're asking it here.

I also suspect you've quoted the question incorrectly. Is "100n2"
supposd to be 100 * n * n?

--
Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

Keith Thompson, Oct 18, 2007

3. ### Richard HeathfieldGuest

Keith Thompson said:

> ashu <> writes:
>> there is question :
>> What is the smallest value of n such that an algorithm whose running
>> time is 100n2 runs faster than an algorithm whose running time is 2n
>> on the same machine.
>>
>> i can`t understand this question plz help me

>
>
> In any case, this isn't a question about the C programming language,
> so I don't know why you're asking it here.
>
> I also suspect you've quoted the question incorrectly. Is "100n2"
> supposd to be 100 * n * n?

I expect so. And presumably 2n supposed to be 2 to the power n.

It may help the OP to recognise that the question, as asked (i.e. in the
absence of big-O notation, which IMHO would in any case make the question
meaningless), is looking for the integer value of n that is just higher
than the real value that is the solution to the following equation:

2 to the power n = 100 * n * n

This is a simple mathematical exercise. It may also be useful to realise
that, when n is set to the correct value, both 2 to the power n and 100 *
n * n easily fit in an unsigned long int. (Yes, I know, but I don't want
to be more specific than that, because it would give too much information;
what I have given, however, should enable the OP to recognise that this
problem can be solved with a very, very, very simple C program.)

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
"Usenet is a strange place" - dmr 29 July 1999

Richard Heathfield, Oct 18, 2007
4. ### Dik T. WinterGuest

In article <> lid writes:
....
> It may help the OP to recognise that the question, as asked (i.e. in the
> absence of big-O notation, which IMHO would in any case make the question
> meaningless), is looking for the integer value of n that is just higher
> than the real value that is the solution to the following equation:
>
> 2 to the power n = 100 * n * n
>
> This is a simple mathematical exercise.

Finding the real value is not exactly a simple mathematical exercise. The
the actual question is not a mathematical exercise at all, just plug in
numbers until you get the answer. Off-hand I have no idea how to formulate
the mathematical answer, but I think it is:
ceiling(exp(-W(-2*log(log(2)/100)/2)))
where W is Lambert's W-function. But I can be wrong, if you have
mathematica on your computer, you can check it.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/

Dik T. Winter, Oct 22, 2007
5. ### Richard HeathfieldGuest

Dik T. Winter said:

> In article <> lid
> writes: ...
> > It may help the OP to recognise that the question, as asked (i.e. in
> > the absence of big-O notation, which IMHO would in any case make the
> > question meaningless), is looking for the integer value of n that is
> > just higher than the real value that is the solution to the following
> > equation:
> >
> > 2 to the power n = 100 * n * n
> >
> > This is a simple mathematical exercise.

>
> Finding the real value is not exactly a simple mathematical exercise.

It isn't? Using a simple iterative technique, I found the answer in nothing
flat (actually about 3 milliseconds), getting agreement in 2^n and 100n^2
to ten decimal places. Given that we only *need* it to one decimal place,
I'd have thought that was an adequate solution.

I suspect we are using different definitions of "mathematical".

<snip>

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
"Usenet is a strange place" - dmr 29 July 1999

Richard Heathfield, Oct 22, 2007
6. ### CBFalconerGuest

Richard Heathfield wrote:
> Dik T. Winter said:
>> lid writes:
>>
>>> It may help the OP to recognise that the question, as asked (i.e.
>>> in the absence of big-O notation, which IMHO would in any case
>>> make the question meaningless), is looking for the integer value
>>> of n that is just higher than the real value that is the solution
>>> to the following equation:
>>>
>>> 2 to the power n = 100 * n * n
>>>
>>> This is a simple mathematical exercise.

>>
>> Finding the real value is not exactly a simple mathematical
>> exercise.

>
> It isn't? Using a simple iterative technique, I found the answer
> in nothing flat (actually about 3 milliseconds), getting agreement
> in 2^n and 100n^2 to ten decimal places. Given that we only *need*
> it to one decimal place, I'd have thought that was an adequate
> solution.

Taking log2() function of both sides, we have:

n = log2(100) + 2 * log2(n)

which makes it fairly easy to divide integers into two classes,
i.e. those where "n < log2(100) + 2*log2(n)" and those where "n >
log2(100) + 2*log2(n)". Note that the equality condition cannot
occur since 2 does not contain all the factors of 100. We can go
close to exactness by considering 100 as 2*2*5*5, so that log2(100)
= 2 + 2* log2(5), and that result is obviously greater than 6 and
less than 7.

All this should be obvious to any child of 10 who has passed the
kindergarten class on logarithms.

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

CBFalconer, Oct 22, 2007
7. ### Dik T. WinterGuest

In article <> lid writes:
> Dik T. Winter said:
>
> > In article <> lid
> > writes: ...
> > > It may help the OP to recognise that the question, as asked (i.e. in
> > > the absence of big-O notation, which IMHO would in any case make the
> > > question meaningless), is looking for the integer value of n that is
> > > just higher than the real value that is the solution to the following
> > > equation:
> > >
> > > 2 to the power n = 100 * n * n
> > >
> > > This is a simple mathematical exercise.

> >
> > Finding the real value is not exactly a simple mathematical exercise.

>
> It isn't? Using a simple iterative technique, I found the answer in nothing
> flat (actually about 3 milliseconds), getting agreement in 2^n and 100n^2
> to ten decimal places. Given that we only *need* it to one decimal place,
> I'd have thought that was an adequate solution.
>
> I suspect we are using different definitions of "mathematical".

No. The difference is between finding a value and finding an approximation
to a value.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/

Dik T. Winter, Oct 22, 2007
8. ### Richard HeathfieldGuest

Dik T. Winter said:

> In article <> lid
> writes:
> > Dik T. Winter said:
> >
> > > In article <>
> > > lid writes: ...
> > > > It may help the OP to recognise that the question, as asked (i.e.
> > > > in the absence of big-O notation, which IMHO would in any case
> > > > make the question meaningless), is looking for the integer value
> > > > of n that is just higher than the real value that is the solution
> > > > to the following equation:
> > > >
> > > > 2 to the power n = 100 * n * n
> > > >
> > > > This is a simple mathematical exercise.
> > >
> > > Finding the real value is not exactly a simple mathematical
> > > exercise.

> >
> > It isn't? Using a simple iterative technique, I found the answer in
> > nothing flat (actually about 3 milliseconds), getting agreement in 2^n
> > and 100n^2 to ten decimal places. Given that we only *need* it to one
> > decimal place, I'd have thought that was an adequate solution.
> >
> > I suspect we are using different definitions of "mathematical".

>
> No. The difference is between finding a value and finding an
> approximation to a value.

Fine. Bear in mind, however, that the final value in my original discussion
was an integer value, and it can of course be determined precisely.

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
"Usenet is a strange place" - dmr 29 July 1999

Richard Heathfield, Oct 22, 2007
9. ### Richard HarterGuest

On Mon, 22 Oct 2007 14:36:55 GMT, "Dik T. Winter"
<> wrote:

>In article <> lid writes:
> > Dik T. Winter said:
> >
> > > In article <> lid
> > > writes: ...
> > > > It may help the OP to recognise that the question, as asked (i.e. in
> > > > the absence of big-O notation, which IMHO would in any case make the
> > > > question meaningless), is looking for the integer value of n that is
> > > > just higher than the real value that is the solution to the following
> > > > equation:
> > > >
> > > > 2 to the power n = 100 * n * n
> > > >
> > > > This is a simple mathematical exercise.
> > >
> > > Finding the real value is not exactly a simple mathematical exercise.

> >
> > It isn't? Using a simple iterative technique, I found the answer in nothing
> > flat (actually about 3 milliseconds), getting agreement in 2^n and 100n^2
> > to ten decimal places. Given that we only *need* it to one decimal place,
> > I'd have thought that was an adequate solution.
> >
> > I suspect we are using different definitions of "mathematical".

>
>No. The difference is between finding a value and finding an approximation
>to a value.

And the computer on which you can express that value is?

Richard Harter,
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

Richard Harter, Oct 22, 2007
10. ### user923005Guest

On Oct 22, 3:37 pm, (Richard Harter) wrote:
> On Mon, 22 Oct 2007 14:36:55 GMT, "Dik T. Winter"
>
>
>
>
>
> <> wrote:
> >In article <> writes:
> > > Dik T. Winter said:

>
> > > > In article <>
> > > > writes: ...
> > > > > It may help the OP to recognise that the question, as asked (i.e. in
> > > > > the absence of big-O notation, which IMHO would in any case make the
> > > > > question meaningless), is looking for the integer value of n that is
> > > > > just higher than the real value that is the solution to the following
> > > > > equation:

>
> > > > > 2 to the power n = 100 * n * n

>
> > > > > This is a simple mathematical exercise.

>
> > > > Finding the real value is not exactly a simple mathematical exercise.

>
> > > It isn't? Using a simple iterative technique, I found the answer in nothing
> > > flat (actually about 3 milliseconds), getting agreement in 2^n and 100n^2
> > > to ten decimal places. Given that we only *need* it to one decimal place,
> > > I'd have thought that was an adequate solution.

>
> > > I suspect we are using different definitions of "mathematical".

>
> >No. The difference is between finding a value and finding an approximation
> >to a value.

>
> And the computer on which you can express that value is?

I'm not sure what all the fuss is about, it's a parabola, with roots
at 0.0 and 0.02.[*]

[*] which is, of course, utter bologna. Both equations have a
constant of proportionality, which means that the solution could be
any real number. (Assuming 2*n and not 2^n) ;-)

OK, maybe 1.432472784e+001 given some "other interpretation". Give or
take a constant factor as large or small as you like.

P.S.
Keith Briggs has a nifty LambertW function on his web site (or used to
at least).

user923005, Oct 23, 2007
11. ### user923005Guest

On Oct 21, 7:32 pm, "Dik T. Winter" <> wrote:
> In article <> writes:
>
> ...
> > It may help the OP to recognise that the question, as asked (i.e. in the
> > absence of big-O notation, which IMHO would in any case make the question
> > meaningless), is looking for the integer value of n that is just higher
> > than the real value that is the solution to the following equation:
> >
> > 2 to the power n = 100 * n * n
> >
> > This is a simple mathematical exercise.

>
> Finding the real value is not exactly a simple mathematical exercise. The
> the actual question is not a mathematical exercise at all, just plug in
> numbers until you get the answer. Off-hand I have no idea how to formulate
> the mathematical answer, but I think it is:
> ceiling(exp(-W(-2*log(log(2)/100)/2)))
> where W is Lambert's W-function. But I can be wrong, if you have
> mathematica on your computer, you can check it.

I must have gone off somewhere.

> y:= 100 * n * n - 2 ^ n;

2 n
y := 100 n - 2

> fsolve(y, n, -1..100);

14.32472784

> plot(y, n = 5..16);
>

> z := (exp(-LambertW(-2*log(log(2)/100)/2))) ;

z := exp(-LambertW(-ln(1/100 ln(2))))

> evalf(");

.2662051936

>

I got the same answer with this:

/*

************************************************************************
* C math library
* function ZEROIN - obtain a function zero within the given range
*
* Input
* double zeroin(ax,bx,f,tol)
* double ax; Root will be seeked for within
* double bx; a range [ax,bx]
* double (*f)(double x); Name of the function whose
zero
* will be seeked for
* double tol; Acceptable tolerance for the
root
* value.
* May be specified as 0.0 to
cause
* the program to find the root
as
* accurate as possible
*
* Output
* Zeroin returns an estimate for the root with accuracy
* 4*EPSILON*abs(x) + tol
*
* Algorithm
* G.Forsythe, M.Malcolm, C.Moler, Computer methods for
mathematical
* computations. M., Mir, 1980, p.180 of the Russian edition
*
* The function makes use of the bissection procedure combined
with
* the linear or quadric inverse interpolation.
* At every step program operates on three abscissae - a, b, and
c.
* b - the last and the best approximation to the root
* a - the last but one approximation
* c - the last but one or even earlier approximation than a that
* 1) |f(b)| <= |f(c)|
* 2) f(b) and f(c) have opposite signs, i.e. b and c
confine
* the root
* At every step Zeroin selects one of the two new
approximations, the
* former being obtained by the bissection procedure and the
latter
* resulting in the interpolation (if a,b, and c are all
different
* the quadric interpolation is utilized, otherwise the linear
one).
* If the latter (i.e. obtained by the interpolation) point is
* reasonable (i.e. lies within the current interval [b,c] not
being
* too close to the boundaries) it is accepted. The bissection
result
* is used in the other case. Therefore, the range of uncertainty
is
* ensured to be reduced at least by the factor 1.6
*

************************************************************************
*/

#include <math.h>
#include <stdio.h>
#include <float.h>

/* An estimate to the root */
/* ax Left border | of the range */
/* bx Right border| the root is seeked */
/* f() Function under investigation */
/* tol Acceptable tolerance */
double zeroin(double ax, double bx, double (*f) (double),
double tol)
{
double a,
b,
c; /* Abscissae, descr. see above */
double fa; /* f(a) */
double fb; /* f(b) */
double fc; /* f(c) */

if (tol < 0) {
tol = -tol;
puts("negative tol not allowed. Using abs(tol)");
}
if (bx < ax) {
double tmp = bx;
bx = ax;
ax = tmp;
puts("interval was reversed. Using [bx, ax] instead of [ax,
bx]");
}
a = ax;
b = bx;
fa = (*f) (a);
fb = (*f) (b);
c = a;
fc = fa;
/* Main iteration loop */
for (; {
/* Distance from the last but one to the last approximation */
double prev_step = b - a;
double tol_act;/* Actual tolerance */
double p; /* Interpolation step is calcu- */
double q; /* lated in the form p/q; divi- */
/* sion operations is delayed */
/* until the last moment */
double new_step; /* Step at this iteration */

if (fabs(fc) < fabs(fb)) { /* Swap data for b to be the
*/
a = b;
b = c;
c = a; /* best approximation */
fa = fb;
fb = fc;
fc = fa;
}
tol_act = 2 * DBL_EPSILON * fabs(b) + tol / 2;
new_step = (c - b) / 2;

/* BUGBUG: DRC --------------------------------------- */
/* Here, testing a double for equality is a good idea. */
/* BUGBUG: DRC --------------------------------------- */
if (fabs(new_step) <= tol_act || fb == 0.0)
return b; /* Acceptable approx. is found */

/* Decide if the interpolation can be tried */
if (fabs(prev_step) >= tol_act /* If prev_step was large
enough */
&& fabs(fa) > fabs(fb)) { /* and was in true direction,
*/
/* Interpolatiom may be tried */
register double t1,
cb,
t2;
cb = c - b;
/* If only two distinct points, linear interpolation */
/* can only be applied. */
/* BUGBUG: DRC ------------------------------------------
*/
/* This test for equality is questionable. If very, very
*/
/* close to linear, we may have large calculation errors.
*/
/* (Or so it seems to me). Perhaps Dik Winter can help.
*/
/* BUGBUG: DRC ------------------------------------------
*/
if (a == c) {
t1 = fb / fa;
p = cb * t1;
q = 1.0 - t1;
} else { /* Quadric inverse interpolation */
q = fa / fc;
t1 = fb / fc;
t2 = fb / fa;
p = t2 * (cb * q * (q - t1) - (b - a) * (t1 - 1.0));
q = (q - 1.0) * (t1 - 1.0) * (t2 - 1.0);
}
if (p > 0.0) /* p was calculated with the op- */
q = -q; /* posite sign; make p positive */
else /* and assign possible minus to */
p = -p; /* q */

/* If b+p/q falls in [b,c] and isn't too large it is
accepted */
if (p < (0.75 * cb * q - fabs(tol_act * q) / 2)
&& p < fabs(prev_step * q / 2))
new_step = p / q;
/* If p/q is too large then the bissection procedure can
*/
/* reduce [b,c] range further */
}
if (fabs(new_step) < tol_act) /* Adjust the step to be not
less */
if (new_step > (double) 0) /* than tolerance */
new_step = tol_act;
else
new_step = -tol_act;
a = b;
fa = fb; /* Save the previous approx. */
b += new_step;
fb = (*f) (b); /* Do step to a new approxim. */

/* Adjust c for it to have a sign opposite to that of b */
if ((fb > 0 && fc > 0) || (fb < 0 && fc < 0)) {
c = a;
fc = fa;
}
}
}
#ifdef UNIT_TEST
/*

*=======================================================================
* Verify ZEROIN routine
*/
double zeroin(double ax, double bx, double (*f) (double),
double tol);

static int counter; /* Iteration counter */

/* Run a test. */
/* [a,b]=interval containing a root (sign change) */
/* f = function */
/* msg = explanation message */
static void testz(double a, double b, double (*f) (double), char
*msg)
{
double root;
counter = 0;
printf("\nFor function %s\nin [%g,%g] root is\t%.9e\n", msg, a, b,
(root = zeroin(a, b, f, 0.0)));
printf("Function value at the root found\t%.4e\nNo. of iterations\t
\t%d\n",
(*f) (root), counter);
}

static double f1(double x)
{ /* test of the Forsythe book */
counter++;
return (x*x - 2.0) * x - 5.0;
}

static double f2(double x)
{ /* My test */
counter++;
return cos(x) - x;
}

static double f3(double x)
{ /* My test */
counter++;
return sin(x) - x;
}

static double f4(double x)
{ /* My test */
x = 0.17875/(1-0.05/x*(1-exp(-7*x)))-0.164-x;
return x;
}

static double f5(double x)
{ /* My test */
return 100.0 * x * x - pow(2.0, x);
}

int main(void)
{
puts("testing zero finder.");
testz(2.0, 3.0, f1, "x^3 - 2*x - 5");
printf("Exact root is \t\t2.0945514815\n");

testz(2.0, 3.0, f2, "cos(x)-x");
testz(-1.0, 3.0, f2, "cos(x)-x");
testz(-1.0, 3.0, f3, "sin(x)-x");
testz(-1.e29, 1e30, f4, "0.17875/(1-0.05/x*(1-exp(-7*x)))-0.164-
x");
testz(-10.0, 10000.0, f5, "100 * n * n - 2 ^ n");
return 0;
}
#endif

user923005, Oct 23, 2007
12. ### user923005Guest

On Oct 22, 3:37 pm, (Richard Harter) wrote:
> On Mon, 22 Oct 2007 14:36:55 GMT, "Dik T. Winter"
>
>
>
>
>
> <> wrote:
> >In article <> writes:
> > > Dik T. Winter said:

>
> > > > In article <>
> > > > writes: ...
> > > > > It may help the OP to recognise that the question, as asked (i.e. in
> > > > > the absence of big-O notation, which IMHO would in any case make the
> > > > > question meaningless), is looking for the integer value of n that is
> > > > > just higher than the real value that is the solution to the following
> > > > > equation:

>
> > > > > 2 to the power n = 100 * n * n

>
> > > > > This is a simple mathematical exercise.

>
> > > > Finding the real value is not exactly a simple mathematical exercise.

>
> > > It isn't? Using a simple iterative technique, I found the answer in nothing
> > > flat (actually about 3 milliseconds), getting agreement in 2^n and 100n^2
> > > to ten decimal places. Given that we only *need* it to one decimal place,
> > > I'd have thought that was an adequate solution.

>
> > > I suspect we are using different definitions of "mathematical".

>
> >No. The difference is between finding a value and finding an approximation
> >to a value.

>
> And the computer on which you can express that value is?

If you give it in terms of an equation, then you can easily accomplish
it symbolically.

user923005, Oct 23, 2007
13. ### Richard HarterGuest

On Mon, 22 Oct 2007 18:17:01 -0700, user923005
<> wrote:

>On Oct 22, 3:37 pm, (Richard Harter) wrote:
>> On Mon, 22 Oct 2007 14:36:55 GMT, "Dik T. Winter"
>>
>>
>>
>>
>>
>> <> wrote:
>> >In article <> writes:
>> > > Dik T. Winter said:

>>
>> > > > In article <>
>> > > > writes: ...
>> > > > > It may help the OP to recognise that the question, as asked (i.e. in
>> > > > > the absence of big-O notation, which IMHO would in any case make the
>> > > > > question meaningless), is looking for the integer value of n that is
>> > > > > just higher than the real value that is the solution to the following
>> > > > > equation:

>>
>> > > > > 2 to the power n = 100 * n * n

>>
>> > > > > This is a simple mathematical exercise.

>>
>> > > > Finding the real value is not exactly a simple mathematical exercise.

>>
>> > > It isn't? Using a simple iterative technique, I found the answer in nothing
>> > > flat (actually about 3 milliseconds), getting agreement in 2^n and 100n^2
>> > > to ten decimal places. Given that we only *need* it to one decimal place,
>> > > I'd have thought that was an adequate solution.

>>
>> > > I suspect we are using different definitions of "mathematical".

>>
>> >No. The difference is between finding a value and finding an approximation
>> >to a value.

>>
>> And the computer on which you can express that value is?

>
>If you give it in terms of an equation, then you can easily accomplish
>it symbolically.
>

Granted. However Dik wrote "Finding the real value" which is not
the same thing as finding either an approximation or a symbolic
expression. In other words he was asking for something that
cannot be produced either by a computer or a human being, even
though it can be done by a mathematician.

Richard Harter,
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

Richard Harter, Oct 23, 2007
14. ### user923005Guest

On Oct 22, 9:17 pm, (Richard Harter) wrote:
> On Mon, 22 Oct 2007 18:17:01 -0700, user923005
>
>
>
>
>
> <> wrote:
> >On Oct 22, 3:37 pm, (Richard Harter) wrote:
> >> On Mon, 22 Oct 2007 14:36:55 GMT, "Dik T. Winter"

>
> >> <> wrote:
> >> >In article <> writes:
> >> > > Dik T. Winter said:

>
> >> > > > In article <>
> >> > > > writes: ...
> >> > > > > It may help the OP to recognise that the question, as asked (i.e. in
> >> > > > > the absence of big-O notation, which IMHO would in any case make the
> >> > > > > question meaningless), is looking for the integer value of n that is
> >> > > > > just higher than the real value that is the solution to the following
> >> > > > > equation:

>
> >> > > > > 2 to the power n = 100 * n * n

>
> >> > > > > This is a simple mathematical exercise.

>
> >> > > > Finding the real value is not exactly a simple mathematical exercise.

>
> >> > > It isn't? Using a simple iterative technique, I found the answer in nothing
> >> > > flat (actually about 3 milliseconds), getting agreement in 2^n and 100n^2
> >> > > to ten decimal places. Given that we only *need* it to one decimal place,
> >> > > I'd have thought that was an adequate solution.

>
> >> > > I suspect we are using different definitions of "mathematical".

>
> >> >No. The difference is between finding a value and finding an approximation
> >> >to a value.

>
> >> And the computer on which you can express that value is?

>
> >If you give it in terms of an equation, then you can easily accomplish
> >it symbolically.

>
> Granted. However Dik wrote "Finding the real value" which is not
> the same thing as finding either an approximation or a symbolic
> expression. In other words he was asking for something that
> cannot be produced either by a computer or a human being, even
> though it can be done by a mathematician.

I disagree.
I can print the exact value of the ratio of the circumference to the
diameter as:
#include <stdio.h>
int main(void)
{
puts("pi");
return 0;
}

Dik did something like that up above. I did not get the same answer
as him numerically (which means *for sure* what I did was wrong) but
his symbolic expression {if correct} is the exact mathematical answer.

user923005, Oct 23, 2007
15. ### Dik T. WinterGuest

In article <> (Richard Harter) writes:
> On Mon, 22 Oct 2007 14:36:55 GMT, "Dik T. Winter"
> <> wrote:

....
> > > I suspect we are using different definitions of "mathematical".

> >
> >No. The difference is between finding a value and finding an approximation
> >to a value.

>
> And the computer on which you can express that value is?

Strange, I thought that in a previous article I gave that value.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/

Dik T. Winter, Oct 23, 2007
16. ### Dik T. WinterGuest

In article <> user923005 <> writes:
> On Oct 21, 7:32 pm, "Dik T. Winter" <> wrote:
> > In article <> writes:

....
> > > than the real value that is the solution to the following equation:
> > >
> > > 2 to the power n = 100 * n * n
> > >
> > > This is a simple mathematical exercise.

> >
> > Finding the real value is not exactly a simple mathematical exercise. The
> > the actual question is not a mathematical exercise at all, just plug in
> > numbers until you get the answer. Off-hand I have no idea how to formulate
> > the mathematical answer, but I think it is:
> > ceiling(exp(-W(-2*log(log(2)/100)/2)))
> > where W is Lambert's W-function. But I can be wrong, if you have
> > mathematica on your computer, you can check it.

>
> I must have gone off somewhere.

I had gone off somewhere. The actual solution is:
sqrt(exp(-W(-log(2)/20)))/10.

Note however, that if you take the principal value of the W function
the result is 0.1036578164 (which is indeed also a solution). You
need the value on another branch. In Maple that would be
sqrt(exp(LambertW(-1, -log(2)/20)))/10.
and then you get:
> 14.32472784

approximately.

(Yes, it is not trivial...)
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/

Dik T. Winter, Oct 23, 2007
17. ### Richard HarterGuest

On Tue, 23 Oct 2007 10:32:01 GMT, "Dik T. Winter"
<> wrote:

>In article <> (Richard Harter) writes:
> > On Mon, 22 Oct 2007 14:36:55 GMT, "Dik T. Winter"
> > <> wrote:

>...
> > > > I suspect we are using different definitions of "mathematical".
> > >
> > >No. The difference is between finding a value and finding an approximation
> > >to a value.

> >
> > And the computer on which you can express that value is?

>
>Strange, I thought that in a previous article I gave that value.

Well, no, you gave an expression that would yield the value if
evaluated with infinite precision. Not at all the same thing as
the real value.

Richard Harter,
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

Richard Harter, Oct 23, 2007
18. ### Dik T. WinterGuest

In article <> (Richard Harter) writes:
> On Tue, 23 Oct 2007 10:32:01 GMT, "Dik T. Winter"
> <> wrote:

....
> > > And the computer on which you can express that value is?

> >
> >Strange, I thought that in a previous article I gave that value.

>
> Well, no, you gave an expression that would yield the value if
> evaluated with infinite precision. Not at all the same thing as
> the real value.

In mathematics it is. Each real value has many representations, and
not necessarily each representation is some finite numerical representation.
So when asked for the solution of x**2 = 2, the mathematical result is
+sqrt(2) or -sqrt(2), and they are the real values.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/

Dik T. Winter, Oct 24, 2007
19. ### Richard HarterGuest

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

>In article <> (Richard Harter) writes:
> > On Tue, 23 Oct 2007 10:32:01 GMT, "Dik T. Winter"
> > <> wrote:

>...
> > > > And the computer on which you can express that value is?
> > >
> > >Strange, I thought that in a previous article I gave that value.

> >
> > Well, no, you gave an expression that would yield the value if
> > evaluated with infinite precision. Not at all the same thing as
> > the real value.

>
>In mathematics it is.

Well, no, it is not.

>Each real value has many representations, and
>not necessarily each representation is some finite numerical representation.
>So when asked for the solution of x**2 = 2, the mathematical result is
>+sqrt(2) or -sqrt(2), and they are the real values.

No, they aren't the real values - they are representations of the
real values.

Richard Harter,
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

Richard Harter, Oct 24, 2007
20. ### CBFalconerGuest

Richard Harter wrote:
> <> wrote:
>

.... snip ...
>
>> Each real value has many representations, and not necessarily
>> each representation is some finite numerical representation. So
>> when asked for the solution of x**2 = 2, the mathematical result
>> is +sqrt(2) or -sqrt(2), and they are the real values.

>
> No, they aren't the real values - they are representations of the
> real values.

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.

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

CBFalconer, Oct 24, 2007