time complexity

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

  1. ashu

    ashu Guest

    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
    #1
    1. Advertising

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


    Ask your instructor for help. This is homework, right?

    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
    #2
    1. Advertising

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

    >
    > Ask your instructor for help. This is homework, right?
    >
    > 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@
    Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
    "Usenet is a strange place" - dmr 29 July 1999
     
    Richard Heathfield, Oct 18, 2007
    #3
  4. 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
    answer includes Lambert's W-function... Actually, finding the answer to
    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
    #4
  5. 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@
    Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
    "Usenet is a strange place" - dmr 29 July 1999
     
    Richard Heathfield, Oct 22, 2007
    #5
  6. ashu

    CBFalconer Guest

    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
    #6
  7. 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
    #7
  8. 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@
    Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
    "Usenet is a strange place" - dmr 29 July 1999
     
    Richard Heathfield, Oct 22, 2007
    #8
  9. 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
    #9
  10. ashu

    user923005 Guest

    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
    #10
  11. ashu

    user923005 Guest

    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
    > answer includes Lambert's W-function... Actually, finding the answer to
    > 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
    #11
  12. ashu

    user923005 Guest

    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
    #12
  13. 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
    #13
  14. ashu

    user923005 Guest

    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
    #14
  15. 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
    #15
  16. 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
    > > answer includes Lambert's W-function... Actually, finding the answer to
    > > 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
    #16
  17. 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
    #17
  18. 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
    #18
  19. 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
    #19
  20. ashu

    CBFalconer Guest

    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
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Time Complexity

    , Jul 11, 2006, in forum: C Programming
    Replies:
    9
    Views:
    450
    Martin Ambuhl
    Jul 11, 2006
  2. Replies:
    2
    Views:
    665
    red floyd
    Jun 12, 2006
  3. Lionel B
    Replies:
    26
    Views:
    1,099
    P.J. Plauger
    Feb 3, 2007
  4. dondora

    time complexity

    dondora, Sep 16, 2007, in forum: C++
    Replies:
    2
    Views:
    916
  5. youtoo
    Replies:
    3
    Views:
    832
    youtoo
    Jul 22, 2008
Loading...

Share This Page