Re: Alternate sum mistake

Discussion in 'C Programming' started by Eric Sosman, Oct 17, 2010.

  1. Eric Sosman

    Eric Sosman Guest

    On 10/17/2010 10:23 AM, superpollo wrote:
    > superpollo ha scritto:
    >> superpollo ha scritto:
    >>> hi.
    >>>
    >>> i submitted some code to an automatic judge:
    >>>
    >>> Question. Please write a c function add_up(int a[], int p),
    >>> which takes a list a of p integers
    >>>
    >>> a[0],...,a[n],...,a[p-1]
    >>>
    >>> (where p varies between 3 and 500), and returns the sum of
    >>> (-1)^n*a[n] for the first 24 indices n (or the whole list if
    >>> p < 24).
    >>>
    >>> i submitted this:
    >>>
    >>> #include <math.h>
    >>> #include <stdlib.h>
    >>> int add_up(int a[], int p) {
    >>> int as,n;
    >>> for(as=0,n=0;n<24;as+=pow(-1,n)*a[n++]);
    >>> return as;
    >>> }
    >>>
    >>> and the response was:
    >>>
    >>> Your code passes the tests: NO
    >>>
    >>> Your code didn't pass the test on the following list of
    >>> 3 integers:
    >>>
    >>> -3, 0, -711
    >>>
    >>> It returns 51734, while the right result should be -714.
    >>>
    >>> where is the mistake? i know i did not check for the 24 limit,
    >>> but that should not be the case since the test was executed upon
    >>> a 3-element-array.

    >>
    >> now that i think of it ... this is *EXACTLY* the case! please excuse
    >> me...

    >
    > so that:
    >
    > for(as=0,n=0;n<24&&n<p;as+=pow(-1,n)*a[n++]);
    > ^^^^^
    >
    > now passes the test :)


    An important lesson to learn about software: "Passes the test"
    is not the same as "Is correct." As Dijkstra put it, "Program testing
    can be used to show the presence of bugs, but never to show their absence!"

    There's at least one more bug in your code, a bug that a C test
    framework might or might not reveal. Can you spot it? (Hint: What
    sort of behavior gives rise to "might or might not" conditions in C?)

    (Actually, there's at least one additional sort-of-bug, but it's
    probably due to typographical oddities in the problem description.
    The description calls for computing terms of the form, "(-1)^n*a[n]"
    which you've interpreted as "minus one, to the power n, times a[n]."
    A literal interpretation is "minus one, exclusive-OR'ed with the
    product of n and a[n]." Your interpretation is probably right, since
    the literal version leads to non-portable results, but if the problem
    description is exactly as you've shown you should consider filing a
    bug against it.)

    --
    Eric Sosman
    lid
    Eric Sosman, Oct 17, 2010
    #1
    1. Advertising

  2. Eric Sosman

    Eric Sosman Guest

    On 10/17/2010 11:49 AM, superpollo wrote:
    > superpollo ha scritto:
    >> Eric Sosman ha scritto:
    >>> [...]
    >>> There's at least one more bug in your code, a bug that a C test
    >>> framework might or might not reveal. Can you spot it? (Hint: What
    >>> sort of behavior gives rise to "might or might not" conditions in C?)

    >>
    >> mmhhh... UB maybe?
    >>
    >> but i cannot spot it at once... something related to the ++ operator?

    >
    > as+=pow(-1,n)*a[n++]
    >
    > there is no guarantee on the order of evaluation of the *, right? so
    > a[n++] could be evaluated prior to pow(-1,n), screwing up the sign.
    >
    > close?


    Extremely close indeed: congratulations! You've spotted the error,
    and your only failing is that you've slightly mis-stated its effects.
    It's not just that the order of evaluation is unspecified, but that it
    is Undefined Behavior to both change the value of `n' and use it for
    some other purpose without an intervening sequence point. In principle
    anything at all could happen, although in practice the outcome is likely
    to be as you describe: The second argument to pow() will be either the
    original `n' or the incremented `n', unpredictably. ("Unpredictably"
    not only from one program run to the next, but within a single run: If
    an optimizer unrolls your loop so there are multiple copies of the
    faulty expression in it, there's no surety that all of them behave the
    same way.)

    --
    Eric Sosman
    lid
    Eric Sosman, Oct 17, 2010
    #2
    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. \(beta-\) Frank Nitzsche

    where is the mistake?

    \(beta-\) Frank Nitzsche, Jun 25, 2004, in forum: VHDL
    Replies:
    4
    Views:
    530
  2. Jesse

    Beginner Mistake

    Jesse, Jul 22, 2003, in forum: ASP .Net
    Replies:
    1
    Views:
    359
    Jesse
    Jul 22, 2003
  3. Chris
    Replies:
    2
    Views:
    663
    Chris
    Mar 4, 2007
  4. Ben Bacarisse

    Re: Alternate sum mistake

    Ben Bacarisse, Oct 17, 2010, in forum: C Programming
    Replies:
    7
    Views:
    337
    Ben Bacarisse
    Oct 24, 2010
  5. Replies:
    10
    Views:
    322
    Sean O'Halpin
    Jul 17, 2006
Loading...

Share This Page