Re: PRIME1 (SPOJ)

Discussion in 'C Programming' started by Ben Bacarisse, Oct 19, 2010.

  1. superpollo <> writes:

    > superpollo ha scritto:
    >> ok, the problem is:
    >>
    >> https://www.spoj.pl/problems/PRIME1/

    > ...
    >
    > i think i made kind of an improvment, thanks to suggestion in an
    > italian math newsgroup:


    Because on-line judges don't comment on program style, I'll offer some
    C-related comments. If this were comp.programming, I have things to say
    about the algorithms, but lets keep this about C...

    > #include <stdio.h>
    > #include <stdlib.h>
    > #include <stdbool.h>
    > #define HOWMANYPRIMES 3401
    >
    > unsigned primes[HOWMANYPRIMES] = {
    > 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59,

    <snip lots of primes>
    > 31567, 31573, 31583, 31601, 31607
    > };


    Humans are bad at counting but computers do it well. Rather than tie
    the correctness of the program to all sorts of things being just right
    you can let the compiler help out:

    unsigned primes[] = {
    2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59,
    ...
    31567, 31573, 31583, 31601, 31607
    };

    If you need to know how many primes you've now got you can define this
    afterwards rather than before:

    #define HOWMANYPRIMES (sizeof primes / sizeof primes[0])

    > bool is_prime(unsigned long x)
    > {
    > bool prime;
    > unsigned i;
    > if (x <= 31607) {


    Again, rather than link lots of parts of the program to the maximum
    expected input (31607 is the largest prime less than the sqrt of the
    largest input the program should be able to deal with) you could write

    if (x <= primes[HOWMANYPRIMES - 1]) {

    > prime = false;
    > for (i = 0; i < HOWMANYPRIMES; i++) {
    > if (x == primes) {
    > prime = true;
    > break;
    > }
    > }


    You don't need to test over 3400 primes to know that 6 is not prime.
    Once you see 7 you know that 6 is not there. I know I was not going to
    make algorithmic comments but there is a C issue here: know the standard
    library! There is a function bsearch, that can search a sorted array
    for an item. Whether it pays to use it will depend on the pattern of
    inputs the program gets but it's worth a try.

    > } else {
    > prime = true;
    > for (i = 0; i < HOWMANYPRIMES && primes * primes <= x; i++) {
    > if (!(x % primes)) {
    > prime = false;
    > break;
    > }
    > }
    > }
    > return prime;
    > }


    Rather than use break so much, many C programmers would use an early
    return. The auxiliary bool variable then becomes obsolete:

    bool is_prime(unsigned long x)
    {
    unsigned i;
    if (x <= 31607) {
    for (i = 0; i < HOWMANYPRIMES; i++)
    if (x == primes)
    return true;
    return false;
    }
    else {
    for (i = 0; i < HOWMANYPRIMES && primes * primes <= x; i++)
    if (!(x % primes))
    return false;
    return true;
    }
    }

    Not everyone agrees on this. Look up "single entry single exit" and you
    will probably be able to find some good counter arguments.

    <snip>
    --
    Ben.
     
    Ben Bacarisse, Oct 19, 2010
    #1
    1. Advertising

  2. superpollo <> writes:

    > Ben Bacarisse ha scritto:

    <snip>
    >> Not everyone agrees on this. Look up "single entry single exit" and you
    >> will probably be able to find some good counter arguments.
    >>
    >> <snip>

    >
    > yeah, this sound like some interesting stylistic issue ... if i
    > understand it correctly, it seems like there is a tradeoff between
    > "single exit" and "natural loop termination": cannot have both, yes?


    Well, you can have both -- sometimes but not always. There are examples
    where there is no conflict between them.

    > granted having one auxvar less is an even better deal...


    For me, yes, but I did want you to know that there is some controversy
    here.

    --
    Ben.
     
    Ben Bacarisse, Oct 19, 2010
    #2
    1. Advertising

  3. superpollo <> writes:

    > Ben Bacarisse ha scritto:
    >> superpollo <> writes:
    >>
    >>> Ben Bacarisse ha scritto:

    >> <snip>
    >>>> Not everyone agrees on this. Look up "single entry single exit" and you
    >>>> will probably be able to find some good counter arguments.
    >>>>
    >>>> <snip>
    >>> yeah, this sound like some interesting stylistic issue ... if i
    >>> understand it correctly, it seems like there is a tradeoff between
    >>> "single exit" and "natural loop termination": cannot have both, yes?

    >>
    >> Well, you can have both -- sometimes but not always. There are examples
    >> where there is no conflict between them.

    >
    > can you show me how, in the code:
    >
    > bool is_prime(unsigned long x)
    > {
    > unsigned i;
    > if (x == 1) {
    > return false;
    > } else {
    > for (i = 0; i < HOWMANYPRIMES && primes * primes <= x; i++) {
    > if (!(x % primes)) {
    > return false;
    > }
    > }
    > }
    > return true;
    > }


    It's not possible in all cases. Also, the tension is not always just
    between a natural loop condition and having a signal exit. Let me
    illustrate this with the primes example.

    If you add a sentinel of 1 at the end of the primes array you can write
    the test like this:

    unsigned i = 0;
    while (primes * primes <= x && x % primes)
    ++i;
    return x > 1 && primes > 1;

    Now this has a simple, natural loop but the single exit is with a not
    entirely obvious return value. Is that trade-off worth it? I don't
    know for sure.

    Alternatively you could add a more logical sentinel -- the next prime
    (31627) knowing that no input x will be > 31627*31627. Now you'd write:

    unsigned i = 0;
    while (primes * primes <= x)
    ++i;
    return x > 1 && i < HOWMANYPRIMES - 1;

    Is that any better? Again, I would never be able to say for sure.
    Mentally I ascribe to various parts of the program a cost and I try to
    find the minimum cost solution. Complex loop conditions have a cost
    but, for me, it's lower than the cost of a break. A return from a loop
    has lower "yuck" factor than a break plus an extra variable. The costs
    aren't fixed and it's all very vague -- largely derived from looking at
    code that I've decided I like.

    (I am pretty sure there will be an error in one or both of these
    examples. I've not spent enough time to be sure of them.)
    >
    > ?
    >
    > bye


    --
    Ben.
     
    Ben Bacarisse, Oct 19, 2010
    #3
    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. Shriphani
    Replies:
    2
    Views:
    572
    Ian Kelly
    Jun 1, 2008
  2. bert

    Re: PRIME1 (SPOJ)

    bert, Oct 18, 2010, in forum: C Programming
    Replies:
    4
    Views:
    456
    Michael Foukarakis
    Oct 20, 2010
  3. BartC

    Re: PRIME1 (SPOJ)

    BartC, Oct 19, 2010, in forum: C Programming
    Replies:
    5
    Views:
    530
    BartC
    Oct 19, 2010
  4. Ben Bacarisse

    Re: PRIME1 (SPOJ)

    Ben Bacarisse, Oct 19, 2010, in forum: C Programming
    Replies:
    8
    Views:
    561
    Dann Corbit
    Oct 20, 2010
  5. Dann Corbit

    Re: PRIME1 (SPOJ)

    Dann Corbit, Oct 20, 2010, in forum: C Programming
    Replies:
    2
    Views:
    945
    Dann Corbit
    Oct 20, 2010
Loading...

Share This Page