Velocity Reviews > time complexity

# time complexity

user923005
Guest
Posts: n/a

 10-23-2007
On Oct 21, 7:32 pm, "Dik T. Winter" <(E-Mail Removed)> wrote:
> In article <(E-Mail Removed)> (E-Mail Removed) 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
Guest
Posts: n/a

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

>
> > > > In article <(E-Mail Removed)> (E-Mail Removed)
> > > > 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.

Richard Harter
Guest
Posts: n/a

 10-23-2007
On Mon, 22 Oct 2007 18:17:01 -0700, user923005
<(E-Mail Removed)> wrote:

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

>>
>> > > > In article <(E-Mail Removed)> (E-Mail Removed)
>> > > > 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://www.velocityreviews.com/forums/(E-Mail 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

user923005
Guest
Posts: n/a

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

>
> >> <(E-Mail Removed)> wrote:
> >> >In article <(E-Mail Removed)> (E-Mail Removed) writes:
> >> > > Dik T. Winter said:

>
> >> > > > In article <(E-Mail Removed)> (E-Mail Removed)
> >> > > > 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.

Dik T. Winter
Guest
Posts: n/a

 10-23-2007
In article <(E-Mail Removed)> (E-Mail Removed) (Richard Harter) writes:
> On Mon, 22 Oct 2007 14:36:55 GMT, "Dik T. Winter"
> <(E-Mail Removed)> 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
Guest
Posts: n/a

 10-23-2007
In article <(E-Mail Removed) om> user923005 <(E-Mail Removed)> writes:
> On Oct 21, 7:32 pm, "Dik T. Winter" <(E-Mail Removed)> wrote:
> > In article <(E-Mail Removed)> (E-Mail Removed) 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/

Richard Harter
Guest
Posts: n/a

 10-23-2007
On Tue, 23 Oct 2007 10:32:01 GMT, "Dik T. Winter"
<(E-Mail Removed)> wrote:

>In article <(E-Mail Removed)> (E-Mail Removed) (Richard Harter) writes:
> > On Mon, 22 Oct 2007 14:36:55 GMT, "Dik T. Winter"
> > <(E-Mail Removed)> 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, (E-Mail 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

Dik T. Winter
Guest
Posts: n/a

 10-24-2007
In article <(E-Mail Removed)> (E-Mail Removed) (Richard Harter) writes:
> On Tue, 23 Oct 2007 10:32:01 GMT, "Dik T. Winter"
> <(E-Mail Removed)> 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/

Richard Harter
Guest
Posts: n/a

 10-24-2007
On Wed, 24 Oct 2007 00:58:16 GMT, "Dik T. Winter"
<(E-Mail Removed)> wrote:

>In article <(E-Mail Removed)> (E-Mail Removed) (Richard Harter) writes:
> > On Tue, 23 Oct 2007 10:32:01 GMT, "Dik T. Winter"
> > <(E-Mail Removed)> 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, (E-Mail 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

CBFalconer
Guest
Posts: n/a

 10-24-2007
Richard Harter wrote:
> <(E-Mail Removed)> 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