returning the Fibonacci string separated by comma

Discussion in 'C Programming' started by mac, Feb 13, 2007.

  1. mac

    mac Guest

    Hi,

    I'm trying to write a fibonacci recursive function that will return
    the fibonacci string separated by comma. The problem sounds like this:
    -------------
    Write a recursive function that creates a character string containing
    the first n Fibonacci numbers - F(n) = F(n - 1) + F(n - 2), F(0) =
    F(1) = 1 -, separated by comma. n should be given as an argument to
    the program. The recursive function should only take one parameter, n,
    and should return the string. You will not use any extra function.

    Do not try to optimize for space or speed. Do not assume any maximum
    length for the result string. Also, please don't use global / static
    variables.
    -----------

    The code must be in C. I managed to create a function that returns the
    fibonacci value for the specified 'N' as a char*, but I didn't manage
    to get the entire string separated by comma.
    This is my function:

    char* Recursive(int n){
    char* a = malloc(n*sizeof(char));
    if(n == 0 || n == 1)
    sprintf(a, "%d", n);
    else
    sprintf(a, "%d", atoi(Recursive(n-1)) +
    atoi(Recursive(n-2)));
    return a;
    }


    How could I get the entire string?
    Thanks in advance for help!
    mac, Feb 13, 2007
    #1
    1. Advertising

  2. "mac" <> writes:
    > I'm trying to write a fibonacci recursive function that will return
    > the fibonacci string separated by comma. The problem sounds like this:
    > -------------
    > Write a recursive function that creates a character string containing
    > the first n Fibonacci numbers - F(n) = F(n - 1) + F(n - 2), F(0) =
    > F(1) = 1 -, separated by comma. n should be given as an argument to
    > the program. The recursive function should only take one parameter, n,
    > and should return the string. You will not use any extra function.
    >
    > Do not try to optimize for space or speed. Do not assume any maximum
    > length for the result string. Also, please don't use global / static
    > variables.
    > -----------
    >
    > The code must be in C. I managed to create a function that returns the
    > fibonacci value for the specified 'N' as a char*, but I didn't manage
    > to get the entire string separated by comma.
    > This is my function:
    >
    > char* Recursive(int n){
    > char* a = malloc(n*sizeof(char));
    > if(n == 0 || n == 1)
    > sprintf(a, "%d", n);
    > else
    > sprintf(a, "%d", atoi(Recursive(n-1)) +
    > atoi(Recursive(n-2)));
    > return a;
    > }


    atoi is useless here. What you are doing is first convert integer into
    a string and then back into an integer - waste of time. Moreover, you
    never free memory you allocate. You should first calculate the value
    and then convert it into string:

    #v+
    long fib(int n) {
    return n<2 ? 1 : fib(n-1) + fib(n-2);
    }

    char *fibstr(int n) {
    char *str = malloc(10); /* 10 should be enough */
    /* FIXME: error checking ommited */
    sprintf(str, "%ld", fib(n);
    return str;
    }
    #v-

    Then you can use something like:

    #v+
    for (i = 0; i<=n; ++i) {
    char *str = fibstr(i);
    /* FIXME: need to check buffor size and realloc() if needed */
    sprintf(buf, "%s%s,", buf, str);
    free(str);
    }
    buf[strlen(buf)] = 0;
    #v-

    or even better:

    #v+
    /* FIXME: buffer overflow checking */
    char *fibstr(char *dest, int n) {
    sprintF(dest, "%ld", fib(n));
    return dest;
    }

    char *foo(int n) {
    char str[10];
    /* ... */

    for (i = 0; i<=n; ++i) {
    /* FIXME: need to check buffor size and realloc() if needed */
    sprintf(buf, "%s%s,", buf, fibstr(str, i));
    }
    buf[strlen(buf)] = 0;

    /* ... */
    }
    #v-

    --
    Best regards, _ _
    .o. | Liege of Serenly Enlightened Majesty of o' \,=./ `o
    ..o | Computer Science, Michal "mina86" Nazarewicz (o o)
    ooo +--<mina86*tlen.pl>---<jid:mina86*chrome.pl>--ooO--(_)--Ooo--
    Michal Nazarewicz, Feb 13, 2007
    #2
    1. Advertising

  3. mac

    Chris Dollin Guest

    Michal Nazarewicz wrote:

    > "mac" <> writes:
    >> I'm trying to write a fibonacci recursive function that will return
    >> the fibonacci string separated by comma. The problem sounds like this:
    >> -------------
    >> Write a recursive function that creates a character string containing
    >> the first n Fibonacci numbers - F(n) = F(n - 1) + F(n - 2), F(0) =
    >> F(1) = 1 -, separated by comma. n should be given as an argument to
    >> the program. The recursive function should only take one parameter, n,
    >> and should return the string. You will not use any extra function.
    >>
    >> Do not try to optimize for space or speed. Do not assume any maximum
    >> length for the result string. Also, please don't use global / static
    >> variables.
    >> -----------
    >>
    >> The code must be in C. I managed to create a function that returns the
    >> fibonacci value for the specified 'N' as a char*, but I didn't manage
    >> to get the entire string separated by comma.
    >> This is my function:
    >>
    >> char* Recursive(int n){
    >> char* a = malloc(n*sizeof(char));
    >> if(n == 0 || n == 1)
    >> sprintf(a, "%d", n);
    >> else
    >> sprintf(a, "%d", atoi(Recursive(n-1)) +
    >> atoi(Recursive(n-2)));
    >> return a;
    >> }

    >
    > atoi is useless here.
    > What you are doing is first convert integer into
    > a string and then back into an integer - waste of time.


    "Do not try to optimize for space or speed."

    > Moreover, you
    > never free memory you allocate.


    "Do not try to optimize for space or speed."

    > You should first calculate the value
    > and then convert it into string:
    >
    > #v+
    > long fib(int n) {
    > return n<2 ? 1 : fib(n-1) + fib(n-2);
    > }


    "You will not use any extra function."

    > char *fibstr(int n) {
    > char *str = malloc(10); /* 10 should be enough */
    > /* FIXME: error checking ommited */
    > sprintf(str, "%ld", fib(n);
    > return str;
    > }
    > #v-
    > Then you can use something like:
    >
    > #v+
    > for (i = 0; i<=n; ++i) {
    > char *str = fibstr(i);
    > /* FIXME: need to check buffor size and realloc() if needed */
    > sprintf(buf, "%s%s,", buf, str);
    > free(str);
    > }
    > buf[strlen(buf)] = 0;


    What?

    > #v-
    >
    > or even better:
    >
    > #v+
    > /* FIXME: buffer overflow checking */
    > char *fibstr(char *dest, int n) {
    > sprintF(dest, "%ld", fib(n));
    > return dest;
    > }
    >
    > char *foo(int n) {
    > char str[10];
    > /* ... */
    >
    > for (i = 0; i<=n; ++i) {
    > /* FIXME: need to check buffor size and realloc() if needed */
    > sprintf(buf, "%s%s,", buf, fibstr(str, i));
    > }
    > buf[strlen(buf)] = 0;
    >
    > /* ... */
    > }
    > #v-


    Well, you're going all around the houses for what's a relatively
    straightforward problem, and ignoring the solution conditions
    to boot. (I'm assuming the "extra functions" you're not allowed
    to use aren't C library functions -- otherwise the problem is
    insoluble ...)

    --
    Chris "electric hedgehog" Dollin
    The shortcuts are all full of people using them.
    Chris Dollin, Feb 13, 2007
    #3
  4. mac

    mac Guest

    Chris Dollin wrote:
    > Michal Nazarewicz wrote:
    >
    > > "mac" <> writes:
    > >> I'm trying to write a fibonacci recursive function that will return
    > >> the fibonacci string separated by comma. The problem sounds like this:
    > >> -------------
    > >> Write a recursive function that creates a character string containing
    > >> the first n Fibonacci numbers - F(n) = F(n - 1) + F(n - 2), F(0) =
    > >> F(1) = 1 -, separated by comma. n should be given as an argument to
    > >> the program. The recursive function should only take one parameter, n,
    > >> and should return the string. You will not use any extra function.
    > >>
    > >> Do not try to optimize for space or speed. Do not assume any maximum
    > >> length for the result string. Also, please don't use global / static
    > >> variables.
    > >> -----------
    > >>
    > >> The code must be in C. I managed to create a function that returns the
    > >> fibonacci value for the specified 'N' as a char*, but I didn't manage
    > >> to get the entire string separated by comma.
    > >> This is my function:
    > >>
    > >> char* Recursive(int n){
    > >> char* a = malloc(n*sizeof(char));
    > >> if(n == 0 || n == 1)
    > >> sprintf(a, "%d", n);
    > >> else
    > >> sprintf(a, "%d", atoi(Recursive(n-1)) +
    > >> atoi(Recursive(n-2)));
    > >> return a;
    > >> }

    > >
    > > atoi is useless here.
    > > What you are doing is first convert integer into
    > > a string and then back into an integer - waste of time.

    >
    > "Do not try to optimize for space or speed."
    >
    > > Moreover, you
    > > never free memory you allocate.

    >
    > "Do not try to optimize for space or speed."
    >
    > > You should first calculate the value
    > > and then convert it into string:
    > >
    > > #v+
    > > long fib(int n) {
    > > return n<2 ? 1 : fib(n-1) + fib(n-2);
    > > }

    >
    > "You will not use any extra function."
    >
    > > char *fibstr(int n) {
    > > char *str = malloc(10); /* 10 should be enough */
    > > /* FIXME: error checking ommited */
    > > sprintf(str, "%ld", fib(n);
    > > return str;
    > > }
    > > #v-
    > > Then you can use something like:
    > >
    > > #v+
    > > for (i = 0; i<=n; ++i) {
    > > char *str = fibstr(i);
    > > /* FIXME: need to check buffor size and realloc() if needed */
    > > sprintf(buf, "%s%s,", buf, str);
    > > free(str);
    > > }
    > > buf[strlen(buf)] = 0;

    >
    > What?
    >
    > > #v-
    > >
    > > or even better:
    > >
    > > #v+
    > > /* FIXME: buffer overflow checking */
    > > char *fibstr(char *dest, int n) {
    > > sprintF(dest, "%ld", fib(n));
    > > return dest;
    > > }
    > >
    > > char *foo(int n) {
    > > char str[10];
    > > /* ... */
    > >
    > > for (i = 0; i<=n; ++i) {
    > > /* FIXME: need to check buffor size and realloc() if needed */
    > > sprintf(buf, "%s%s,", buf, fibstr(str, i));
    > > }
    > > buf[strlen(buf)] = 0;
    > >
    > > /* ... */
    > > }
    > > #v-

    >
    > Well, you're going all around the houses for what's a relatively
    > straightforward problem, and ignoring the solution conditions
    > to boot. (I'm assuming the "extra functions" you're not allowed
    > to use aren't C library functions -- otherwise the problem is
    > insoluble ...)
    >
    > --
    > Chris "electric hedgehog" Dollin
    > The shortcuts are all full of people using them.


    The C library functions are allowed ... I'm using strcat, atoi,
    itoa .... but still didn't manage to get it right ... I fell I'm close
    to the solutions ... but yet doesn't work
    mac, Feb 13, 2007
    #4
  5. mac

    Chris Dollin Guest

    mac wrote:

    >
    > Chris Dollin wrote:


    >> (I'm assuming the "extra functions" you're not allowed
    >> to use aren't C library functions -- otherwise the problem is
    >> insoluble ...)


    > The C library functions are allowed ... I'm using strcat, atoi,
    > itoa ....


    `itoa` isn't a Standard C function. I used `sprintf` for the
    job. (And `strtol` rather than `atoi`, because used `long` as
    the type for the fibonacci results.)

    > but still didn't manage to get it right ... I fell I'm close
    > to the solutions ... but yet doesn't work


    Three clues. One: it's not difficult. If your code for this is
    complicated, something is wrong. Two: strings are the poor
    man's lists. Three: write tests [1]. (You can throw them away
    before you submit so they don't count as "extra functions".)

    By the way, the result string can have the numbers in either
    order - largest first or smallest first. I've done largest
    first, but switching order around is trivial. Does it matter?

    [1] OK, OK, so I didn't. My only excuse is that the code worked
    first time [2].

    [2] Not counting missing out a printf argument in the output
    function, and forgetting to compile with enough options.
    Fortunately, `fibs(134514416) = ¨¨®¿ä4` was a bit of a
    giveaway.

    --
    Chris "electric hedgehog" Dollin
    Meaning precedes definition.
    Chris Dollin, Feb 13, 2007
    #5
  6. mac <> wrote:

    > char* Recursive(int n){
    > char* a = malloc(n*sizeof(char));
    > if(n == 0 || n == 1)
    > sprintf(a, "%d", n);
    > else
    > sprintf(a, "%d", atoi(Recursive(n-1)) +
    > atoi(Recursive(n-2)));
    > return a;
    > }


    > How could I get the entire string?
    > Thanks in advance for help!


    You're on the right track. First, think about storing Recursive(n-1)
    and Recursive(n-2) in separate char * variables - you'll need to free
    the memory they point to (at the right time), and you need them both
    to determine the string for (n-1) and to compute the current Fibonacci
    number (as you've done with atoi). Think about what you *really* want
    to return for n == 1 and n == 0. Also think about that call to
    malloc; you aren't malloc'ing enough memory, first of all.

    --
    C. Benson Manica | I *should* know what I'm talking about - if I
    cbmanica(at)gmail.com | don't, I need to know. Flames welcome.
    Christopher Benson-Manica, Feb 13, 2007
    #6
  7. mac

    Chris Dollin Guest

    Christopher Benson-Manica wrote:

    > mac <> wrote:
    >
    >> char* Recursive(int n){
    >> char* a = malloc(n*sizeof(char));
    >> if(n == 0 || n == 1)
    >> sprintf(a, "%d", n);
    >> else
    >> sprintf(a, "%d", atoi(Recursive(n-1)) +
    >> atoi(Recursive(n-2)));
    >> return a;
    >> }

    >
    >> How could I get the entire string?
    >> Thanks in advance for help!

    >
    > You're on the right track. First, think about storing Recursive(n-1)
    > and Recursive(n-2) in separate char * variables - you'll need to free
    > the memory they point to (at the right time),


    He doesn't. That would be an optimisation for space.

    --
    Chris "electric hedgehog" Dollin
    A rock is not a fact. A rock is a rock.
    Chris Dollin, Feb 13, 2007
    #7
  8. Chris Dollin <> wrote:

    > > You're on the right track. First, think about storing Recursive(n-1)
    > > and Recursive(n-2) in separate char * variables - you'll need to free
    > > the memory they point to (at the right time),


    > He doesn't. That would be an optimisation for space.


    I wouldn't personally call avoiding memory leaks an "optimization for
    space", and I wouldn't call a class assigning a homework assignment
    permitting memory leaks in the solution worthwhile. OP's MMV.

    --
    C. Benson Manica | I *should* know what I'm talking about - if I
    cbmanica(at)gmail.com | don't, I need to know. Flames welcome.
    Christopher Benson-Manica, Feb 13, 2007
    #8
  9. mac

    Chris Dollin Guest

    Christopher Benson-Manica wrote:

    > Chris Dollin <> wrote:
    >
    >> > You're on the right track. First, think about storing Recursive(n-1)
    >> > and Recursive(n-2) in separate char * variables - you'll need to free
    >> > the memory they point to (at the right time),

    >
    >> He doesn't. That would be an optimisation for space.

    >
    > I wouldn't personally call avoiding memory leaks an "optimization for
    > space",


    What else is it?

    > and I wouldn't call a class assigning a homework assignment
    > permitting memory leaks in the solution worthwhile. OP's MMV.


    It's not the OP's M; it's their instructor's M. One can reasonably
    assume that the point of the exercise is to learn something about
    recursion and/or Strings For Things; worrying about a space leak
    is a distraction [1]. Maybe the optimisation aspects are the /next/
    lesson.

    It's because we're specifically told that we're not optimising for
    time that I haven't mentioned the exponential pessimisation that
    the code I wrote doesn't have.

    [1] I do wonder if the OPs environment has really thought about
    the language they use for teaching. But in this case I think
    it falls under "don't second-guess the guys at the sharp end".

    --
    Chris "electric hedgehog" Dollin
    Scoring, bah. If I want scoring I'll go play /Age of Steam/.
    Chris Dollin, Feb 13, 2007
    #9
  10. Chris Dollin <> wrote:

    > Christopher Benson-Manica wrote:


    > > I wouldn't personally call avoiding memory leaks an "optimization for
    > > space",


    > What else is it?


    Optimizing for correctness?

    > It's because we're specifically told that we're not optimising for
    > time that I haven't mentioned the exponential pessimisation that
    > the code I wrote doesn't have.


    IMO code can be time-inefficient and still be correct. I don't
    consider code that leaks memory to be correct.

    > [1] I do wonder if the OPs environment has really thought about
    > the language they use for teaching. But in this case I think
    > it falls under "don't second-guess the guys at the sharp end".


    If the goal is to learn about recursion, the problem is a poor one. I
    really don't think there's a good rationale for allowing memory leaks;
    if the class is geared toward non-technology majors, it should be
    tought in a different language, and if it is geared toward technology
    majors it is mis-educating them.

    --
    C. Benson Manica | I *should* know what I'm talking about - if I
    cbmanica(at)gmail.com | don't, I need to know. Flames welcome.
    Christopher Benson-Manica, Feb 13, 2007
    #10
  11. "mac" <> writes:

    > Hi,
    >
    > I'm trying to write a fibonacci recursive function that will return
    > the fibonacci string separated by comma. The problem sounds like this:
    > -------------
    > Write a recursive function that creates a character string containing
    > the first n Fibonacci numbers - F(n) = F(n - 1) + F(n - 2), F(0) =
    > F(1) = 1 -, separated by comma. n should be given as an argument to
    > the program. The recursive function should only take one parameter, n,
    > and should return the string. You will not use any extra function.


    I am not a fan of this sort of restriction. For one, it forces you
    into a particular design, and for another using extra functions is
    almost always A Good Thing.

    > Do not try to optimize for space or speed. Do not assume any maximum
    > length for the result string. Also, please don't use global / static
    > variables.


    If you are not to assume a maximum length, you should not really be
    using integer arithmetic. This is a guess. The problem is rather
    "coded" but if you are to use integer arithmetic (even long long) then
    the strings will be so short that assuming their length would the
    obvious thing to do.

    You know the prototype will be:

    char *fib(int n)

    Write down what fib(0), fib(1)... fib(5) look like. Think what you
    need to do to fib(n-1) to get fib(n). Can you do it without integer
    arithmetic?

    I did it producing the list from fib(1) up to fib(n). It is, I think,
    slightly simpler if you make the list appear from big to small (fib(n)
    to fib(1)). My code is sufficiently bad (no comments and rather
    dubious style in places) that despite this being homework I might
    post it if you post another significant attempt.

    --
    Ben.
    Ben Bacarisse, Feb 13, 2007
    #11
  12. mac

    Guest

    On 13 Feb, 11:50, "mac" <> wrote:
    > Hi,
    >
    > I'm trying to write a fibonacci recursive function that will return
    > the fibonacci string separated by comma. The problem sounds like this:
    > -------------
    > Write a recursive function that creates a character string containing
    > the first n Fibonacci numbers - F(n) = F(n - 1) + F(n - 2), F(0) =
    > F(1) = 1 -, separated by comma. n should be given as an argument to
    > the program. The recursive function should only take one parameter, n,
    > and should return the string. You will not use any extra function.
    >
    > Do not try to optimize for space or speed. Do not assume any maximum
    > length for the result string. Also, please don't use global / static
    > variables.
    > -----------
    >
    > The code must be in C. I managed to create a function that returns the
    > fibonacci value for the specified 'N' as a char*, but I didn't manage
    > to get the entire string separated by comma.
    > This is my function:
    >
    > char* Recursive(int n){
    > char* a = malloc(n*sizeof(char));
    > if(n == 0 || n == 1)
    > sprintf(a, "%d", n);
    > else
    > sprintf(a, "%d", atoi(Recursive(n-1)) +
    > atoi(Recursive(n-2)));
    > return a;
    >
    > }
    >
    > How could I get the entire string?
    > Thanks in advance for help!


    You haven't said exactly what is troubling you, but it looks as though
    you are having difficulties allocating the space for the string. The
    problem says you must not assume a maximum string length, so it looks
    as though you are going to have to keep malloc'ing longer and longer
    spaces until you are finished. This is a bit of an inefficient way of
    going about things, but you have been told you don't need to worry
    about that.

    So I think you need something along the lines of:

    char* Recursive(int n){
    char *a, *b;

    if(n == 0 || n == 1) deal with end of recursion
    a = Recursive(n-1);
    b = malloc(strlen(a) plus a bit more);
    load up b with the contents of a and the new value
    free(a);
    return b;
    }

    This still leaves you to work out how to calculate the new value, of
    course - if you're having trouble with this, make sure you are getting
    the right values, make sure there will always be two of them, and then
    add them up.

    I'd be inclined to include the "free" line, though as Chris says, this
    might be considered an optimisation for space that you aren't allowed
    to do.

    Hope this helps.
    Paul.
    , Feb 13, 2007
    #12
  13. wrote:

    > char* Recursive(int n){
    > char *a, *b;


    > if(n == 0 || n == 1) deal with end of recursion
    > a = Recursive(n-1);
    > b = malloc(strlen(a) plus a bit more);
    > load up b with the contents of a and the new value


    Sounds like a job for "char *c=Recursive(n-2)".

    > free(a);


    And free(c).

    > I'd be inclined to include the "free" line, though as Chris says, this
    > might be considered an optimisation for space that you aren't allowed
    > to do.


    I certainly didn't read the specs as prohibiting optimizations, and as
    I've said elsethread, I disagree with the idea that avoiding memory
    leaks is an "optimization for space".

    --
    C. Benson Manica | I *should* know what I'm talking about - if I
    cbmanica(at)gmail.com | don't, I need to know. Flames welcome.
    Christopher Benson-Manica, Feb 13, 2007
    #13
  14. mac

    Chris Dollin Guest

    Christopher Benson-Manica wrote:

    > Chris Dollin <> wrote:
    >
    >> Christopher Benson-Manica wrote:

    >
    >> > I wouldn't personally call avoiding memory leaks an "optimization for
    >> > space",

    >
    >> What else is it?

    >
    > Optimizing for correctness?


    No, it's certainly not /that/.

    You can leave the `free`s out and the code will produce the correct
    answer string (if malloc doesn't fail, which you have no control
    over anyway). The only reason to put the `free`s in is to reduce
    the space use. That's an optimisation for space.

    Now, I agree that it's a /very important/ optimisation for space,
    and that if the OP's instructor doesn't deal with the issue RSN
    that they're doing them [1] a disservice. But one can't teach
    everything at once.

    >> It's because we're specifically told that we're not optimising for
    >> time that I haven't mentioned the exponential pessimisation that
    >> the code I wrote doesn't have.

    >
    > IMO code can be time-inefficient and still be correct. I don't
    > consider code that leaks memory to be correct.


    I don't see why you can think of space-wasting as "incorrectness"
    and time-wasting as not. If the code takes more than the decreed
    time it's just as incorrect than if it takes more than the decreed
    space.

    My space-wasting implementation of the OP's problem does fib(50)
    in the blink of an eye (and uses only a "little" space per
    outermost call). My space-efficient just-calculate-fib-n
    implementation takes -- oh, it's still running. Hang on a bit.

    >> [1] I do wonder if the OPs environment has really thought about
    >> the language they use for teaching. But in this case I think
    >> it falls under "don't second-guess the guys at the sharp end".

    >
    > If the goal is to learn about recursion, the problem is a poor one.


    Why do you think so? I think the example is pleasingly rich, a lot
    richer than the usual `calculate fib(n) by recursion` stuff we see.
    The string-hacking makes a difference that I /hope/ the instructor
    intends to exploit.

    > I
    > really don't think there's a good rationale for allowing memory leaks;
    > if the class is geared toward non-technology majors, it should be
    > tought in a different language,


    I concur.

    > and if it is geared toward technology
    > majors it is mis-educating them.


    I think (perhaps over-optimistically) that the /explicit/ "don't optimise"
    in the specification means that the optimisation considerations will come
    later. We don't know enough about the instructor and their course to judge
    whether or not it's mis-educating the OP and their co-students.

    [Six minutes. I'm not going to try it on 80.]

    [1] Want. Lojban. Pronouns.

    --
    Chris "electric hedgehog" Dollin
    A rock is not a fact. A rock is a rock.
    Chris Dollin, Feb 14, 2007
    #14
  15. Chris Dollin <> wrote:

    > You can leave the `free`s out and the code will produce the correct
    > answer string (if malloc doesn't fail, which you have no control
    > over anyway). The only reason to put the `free`s in is to reduce
    > the space use. That's an optimisation for space.


    > Now, I agree that it's a /very important/ optimisation for space,
    > ...


    I don't have any good rejoinder to that, so I suppose I'll concede the
    point.

    > I don't see why you can think of space-wasting as "incorrectness"
    > and time-wasting as not.


    Again conceded - I don't believe anyone would characterize bogosort as
    "correct".

    > > If the goal is to learn about recursion, the problem is a poor one.


    > Why do you think so?


    Mainly because it seems to have unnecessarily introduced a new concept
    - memory allocation - which the problem statement suggests the student
    does not yet understand fully.

    > I think (perhaps over-optimistically) that the /explicit/ "don't optimise"
    > in the specification means that the optimisation considerations will come
    > later.


    I would certainly hope so, but even so I would prefer a more logical
    progression of course topics.

    --
    C. Benson Manica | I *should* know what I'm talking about - if I
    cbmanica(at)gmail.com | don't, I need to know. Flames welcome.
    Christopher Benson-Manica, Feb 14, 2007
    #15
  16. mac

    Chris Dollin Guest

    Christopher Benson-Manica wrote:

    > Chris Dollin <> wrote:


    >> I think (perhaps over-optimistically) that the /explicit/ "don't optimise"
    >> in the specification means that the optimisation considerations will come
    >> later.

    >
    > I would certainly hope so, but even so I would prefer a more logical
    > progression of course topics.


    I would put optimisation after doing-something[-useful]. Preferably not
    /long/ after ...

    I wonder if the OP has got anywhere yet?

    --
    Chris "electric hedgehog" Dollin
    "Reaching out for mirrors hidden in the web." - Renaissance, /Running Hard/
    Chris Dollin, Feb 14, 2007
    #16
  17. Chris Dollin <> wrote:

    > I would put optimisation after doing-something[-useful]. Preferably not
    > /long/ after ...


    I still hesitate to call it "optimization" when failing to do it on a
    test will (hopefully) result in points off, and failing to do it on a
    job interview will (hopefully) result in the applicant not being
    hired. I personally prefer do-everything-right ->
    do-something[-useful], but mileage clearly varies here.

    > I wonder if the OP has got anywhere yet?


    Probably long gone, as usual...

    --
    C. Benson Manica | I *should* know what I'm talking about - if I
    cbmanica(at)gmail.com | don't, I need to know. Flames welcome.
    Christopher Benson-Manica, Feb 14, 2007
    #17
  18. mac

    CBFalconer Guest

    Chris Dollin wrote:
    > Christopher Benson-Manica wrote:
    >> Chris Dollin <> wrote:
    >>> Christopher Benson-Manica wrote:

    >>
    >>>> I wouldn't personally call avoiding memory leaks an "optimization
    >>>> for space",

    >>
    >>> What else is it?

    >>
    >> Optimizing for correctness?

    >
    > No, it's certainly not /that/.
    >
    > You can leave the `free`s out and the code will produce the correct
    > answer string (if malloc doesn't fail, which you have no control
    > over anyway). The only reason to put the `free`s in is to reduce
    > the space use. That's an optimisation for space.
    >
    > Now, I agree that it's a /very important/ optimisation for space,
    > and that if the OP's instructor doesn't deal with the issue RSN
    > that they're doing them [1] a disservice. But one can't teach
    > everything at once.
    >
    >>> It's because we're specifically told that we're not optimising
    >>> for time that I haven't mentioned the exponential pessimisation
    >>> that the code I wrote doesn't have.

    >>
    >> IMO code can be time-inefficient and still be correct. I don't
    >> consider code that leaks memory to be correct.

    >
    > I don't see why you can think of space-wasting as "incorrectness"
    > and time-wasting as not. If the code takes more than the decreed
    > time it's just as incorrect than if it takes more than the decreed
    > space.
    >
    > My space-wasting implementation of the OP's problem does fib(50)
    > in the blink of an eye (and uses only a "little" space per
    > outermost call). My space-efficient just-calculate-fib-n
    > implementation takes -- oh, it's still running. Hang on a bit.


    Is the following a space wasting implementation?

    /* returns ULONG_MAX for overflow */
    unsigned long fibo(unsigned int n)
    {
    unsigned long pprev, prev, value;

    if ((pprev = 0) == n) value = pprev;
    else if ((prev = 1) == n) value = prev;
    else do {
    value = pprev + prev; pprev = prev; prev = value;
    if (value < pprev) {
    value = -1; /* ULONG_MAX, overflow */
    goto x;
    }
    } while (2 <= --n);
    x: return value;
    } /* fibo */

    (overflows at 48 for minimum size unsigned long)

    --
    <http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt>
    <http://www.securityfocus.com/columnists/423>

    "A man who is right every time is not likely to do very much."
    -- Francis Crick, co-discover of DNA
    "There is nothing more amazing than stupidity in action."
    -- Thomas Matthews
    CBFalconer, Feb 14, 2007
    #18
    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. Peter Rilling

    Array to a comma Separated String

    Peter Rilling, Jul 8, 2004, in forum: ASP .Net
    Replies:
    3
    Views:
    491
  2. =?Utf-8?B?Q2hyaXMgTGFuZQ==?=

    How to stream a comma separated string to the browser?

    =?Utf-8?B?Q2hyaXMgTGFuZQ==?=, Jul 21, 2006, in forum: ASP .Net
    Replies:
    1
    Views:
    327
    =?Utf-8?B?Q2hyaXMgTGFuZQ==?=
    Jul 21, 2006
  3. ronan_40060

    Parsing a Comma Separated String in C

    ronan_40060, Sep 6, 2006, in forum: C Programming
    Replies:
    1
    Views:
    2,239
    Rudresh R kaddipudi
    Dec 22, 2006
  4. mac
    Replies:
    13
    Views:
    509
    Gavin Deane
    Feb 13, 2007
  5. NickPick
    Replies:
    7
    Views:
    533
    Arne Vajhøj
    Mar 3, 2009
Loading...

Share This Page