i'm sure this must be trivial, remember i'm learning ... program included

Discussion in 'C Programming' started by G G, Sep 21, 2013.

  1. G G

    G G Guest

    this is an exercise from Deitel and Deitel chapter 5 on prime number.
    the problem suggest that there is a speed increase if only the square root
    of the number of comparisons are made to determine if a number is
    prime or not.

    There is, but in my program i noticed that it found less primes. So i must
    have a logic error, in the code, right? it should find the same number of
    primes, just faster. i'm hoping your skill eyes can point out my error. the
    only thing changed is the number of comparisons made to determine if the
    number is prime,

    i created two functions, isThisAPrime (int number), and
    isThisAPrimeSqrt (int number)
    so that if you need to test you only have to change "isThisAPrime...."
    to switch to the other function.

    The total number, of primes, is different between these two functions. they
    should not be. the total number of primes found should be the same. the
    total number of primes maintained by variable numberOfPrimes in the
    program.

    Thanks everyone,

    g.

    -----------------------------------------------------------------

    /* main.c */

    /* exercise5_27.c */

    /*
    * (Prime Numbers)
    * An integer is said to be prime if it’s divisible by
    * only 1 and itself. For ex- ample, 2, 3, 5 and 7 are
    * prime, but 4, 6, 8 and 9 are not.
    *
    * a) Write a function that determines if a number is prime.
    * b) Use this function in a program that determines and
    * prints all the prime numbers between 1 and 10,000. How
    * many of these 10,000 numbers do you really have to test
    * before being sure that you have found all the primes?
    * c) Initially you might think that n/2 is the upper limit
    * for which you must test to see if a number is prime,
    * but you need go only as high as the square root of n.
    * Why? Rewrite the program, and run it both ways. Estimate
    * the performance improvement.
    *
    * written by gdotone
    */

    #include <stdio.h>
    #include <math.h>

    #define LASTNUMBER 1000000 /* changed to note the speed difference */
    #define NUMBEROFCOLUMNS 6 /* number of columns per row printed out */

    /* prototypes */
    int isThisAPrime ( int number ); /* determines if number is prime */
    int isThisAPrimeSqrt (int number ); /* determines if number is prime
    only checking sqrt(number) divisible */

    /*********************** main() ********************************/

    int main ( int argc, char *argv[] )
    {
    int numberOfPrimes = 0; /* used to create number of column rows */
    /* and count the number of primes found */

    for (int i = 1; i < LASTNUMBER; i++ )
    {
    if ( isThisAPrime(i) ) /* change to isThisAPrimeSqrt to use other()*/
    {
    printf("%8d\t", i );
    numberOfPrimes++;
    if ( ( numberOfPrimes % NUMBEROFCOLUMNS ) == 0 )
    printf ("\n");

    } /*end if ( isThisA ... ) */

    } /* end for ( int i ... ) */

    printf("\n %d \n\n", numberOfPrimes);
    return 0;

    } /* end main () */

    /*********************** inThisAPrime() *************************/
    int isThisAPrime ( int number )
    {
    if ( (number == 1) || (number == 5) )
    return 1;
    else if ( ( (number%2) == 0 ) || ( (number%5) == 0 ) )
    return 0;
    else
    {
    for ( int i = 2; i < number; i++ ) /* i < number */
    if ( (number % i) == 0 )
    return 0;

    } /* end else */

    return 1;

    } /* end isThisAPrime ( int ...) */

    /********** isThisAPrimeSqrt() with sqrt(number) used *********/
    int isThisAPrimeSqrt ( int number )
    {
    if ( (number == 1) || (number == 5) )
    return 1;
    else if ( ( (number%2) == 0 ) || ( (number%5) == 0 ) )
    return 0;
    else
    {
    for ( int i = 2; i < sqrt(number); i++ ) /* i < sqrt(number) */
    if ( (number % i) == 0 )
    return 0;

    } /* end else */

    return 1;

    } /* end isThisAPrime ( int ...) */
     
    G G, Sep 21, 2013
    #1
    1. Advertisements

  2. It finds more, not fewer. Well, it prints more numbers -- some of which
    are not prime.
    Yes. In fact both functions have logic errors. In addition to the
    problem you are posting about, neither lists 2, which is a prime, and
    both list 1, which is not.
    Rather just say "here's the problem" I think you'd get more joy finding
    it for yourself. It's not hard. You could write a program prints a
    number only is isThisAPrime(n) != isThisAPrimeSqrt(n). Look at the
    first few numbers -- they all have a very particular property that
    should lead you to the problem right away. It might be even more
    obvious is you removed the special cases from the functions -- the code
    that treats multiples of 2 and 5 separately.

    1 is not prime (basically by conventional agreement), so you should
    remove that special case, but why treat 2 and 5 as special? Why not 2
    and 3, or 2, 3 and 5? At the very least, this is the kind of thing that
    needs a comment. You have lots of comments, but none of them help me
    understand your code -- I know where functions start and where code
    blocks end and so on, but I don't know why 5 is special to you.
    Having tested for divisibility by 2, there is no need to do it again.
    Also, while you need to test for divisibility by 3, do you need to test
    for divisibility by 4? Or by 6? Or 8?
    No, that comment is wrong! That's one reason I never use such comments.

    By the way, a small point, but I prefer to name true/false function by
    the condition of them being true, not as a question. So I'd call the
    function thisIsAPrime (actually I'd call it is_prime, because the "this"
    and the "a" are redundant and I'm old-fashioned about camelCaseNames).
    The effect is to make conditions read more naturally: if (is_prime(n))
    and while (is_prime(x)) ... and so one. It's a matter of style so it is
    ultimately a personal choice (unless you work somewhere with a house
    style).
     
    Ben Bacarisse, Sep 21, 2013
    #2
    1. Advertisements

  3. [prototypes and main program snipped]
    Why do you have special-case tests for 2 and 5? The for loop by itself
    should be enough. If you're thinking that you can save time by avoiding
    the loop in some cases, then (a) you're very likely mistaken, (b) even
    if you're right the performance improvement is likely to be trivial
    (make it right before you make it fast, and *measure*), and (c) you'll
    get more "bang for your buck" by testing 2 and 3 rather than 2 and 5.

    Your for loop tests whether `number` is a multiple of 2, but it never
    will be, since you've already eliminated even numbers.

    And 1 is not generally considered to be a prime number, for mathematical
    reasons going back at least to Euclid.
    Same comments about 1, 2, and 5.

    Take a close look at your for loop, and consider what it will do with
    `number == 49`. It will iterate over potential factors starting with 2,
    considering only number that are *less than* sqrt(49) -- which means it
    won't test 7. The prime numbers this misses are squares of primes other
    than 2 and 5. You want `i <= sqrt(number)`, not `i < sqrt(number)`.

    That should solve the problem you're seeing, but there are some other
    issues. The sqrt() function operates on floating-point numbers, which
    means (a) it's likely to be more expensive than integer operations
    (depending on the system), and (b) it's potentially imprecise. It's
    likely that sqrt() will yield an exact result for an exact integer
    square (for example, sqrt(49) will probably yield exactly 7.0), but
    that's not absolutely guaranteed.

    And you're computing sqrt(number) for every iteration of the loop --
    even though its value never changes. That's expensive.

    If you want to use sqrt(), you should compute it once at the top of the
    loop:

    const int sqrt_n = sqrt(number); /* Note: This converts number from
    int to float and then converts
    the result back from float to
    int */
    for (int i = 2; i <= sqrt_n); i ++)
    ...

    But there's a more reliable way to do the comparison, that avoids any
    floating-point calculations:

    for (int i = 2; i * i <= number; i ++)

    This does perform a multiplication on each iteration, whereas the
    previous version computes sqrt() only once. It's not clear which will
    be faster, but the version that does only integer arithmetic is
    conceptually simpler.
     
    Keith Thompson, Sep 21, 2013
    #3
  4. G G

    G G Guest

    thanks Ben, thanks Keith

    yes, this a cool thought, "...write a program prints a
    number only is isThisAPrime(n) != isThisAPrimeSqrt(n)..."

    will do.
    i cut and pasted, i should be more careful.

    thanks again guys, i really never would have seen those errors.

    g.
     
    G G, Sep 21, 2013
    #4
  5. Others have commented on the program itself.

    I'll say that your approach is right. When you've got a slow and easy way
    of calculating a value, and a fast and tricky way, write the slow and easy
    function first and check it.
    Then write the fast way, and write an automated test to test for maybe
    a minute (it depends on how slow the slow method is) on different values.
    Normally this test is quite easy to write - you just set the input to
    different random numbers. You usually want to test for special cases like 0,
    1, -1 and so on. That reveals any problems.

    You then need to get to the root of any bugs. Don't disguise them or
    code round them. Find out why the function is wrong, and fix the problem
    at source.
     
    Malcolm McLean, Sep 21, 2013
    #5
  6. G G

    G G Guest

    Ben suggestion implemented,
    Keith I found that I needed to add one, 1, to sqrt(number) for the loop
    to execute the correct number of times. I did pull that calculation out
    of the loop control for statement, thanks.

    this seems to work fine. well, no, no, let me say that it finds no values
    that are different in it's quest to tell if the same number it prime ...
    yeah, ok, ok, i know that's a big difference
    from being correct. :)

    i do need to tighten up on my comments in the program. so, i really
    appreciate any and all comment about comments, program clarity.
    my thought was yes, true, no, false in my head i'm trying to think either
    because some code, in the books i'm reading, think yes, no, in those if
    comparisons.
    so i thought isThisAPrime (number) read well. hey, i can change that
    thought though. is_prime(x) is fine. my end goal is to learn and write
    code that you guys read with professional ease. i'm a long way from that
    right now...

    please tell me if my style is out there, too far from the norm.

    thanks again,
    g.
    ben's suggestion program below.

    oh, yeah, the hints and direction to thought is much better than just
    telling me the answer. i'm learning more, well it seems that way. i'm
    sure there will come a time where i just don't understand.

    ----------------------------------------------------------


    /* main.c */

    /* exercise5_27.c */

    /*
    * (Prime Numbers)
    * This program is base on an exercise found in Deitel and Deitel
    * chapter 5.
    *
    **** This program is an incite, passed on by Ben Bacarisse of the *****
    **** Comp.lang.c Group on Google Group, to solve a mistake of ****
    **** which I had in a earlier post to comp.lang.c. This program *****
    **** compares the output of two function that are finding prime *****
    **** numbers. The program prints the number at which there may****
    **** disagreement between the functions *****
    *
    * written by gdotone and with insite for corrections of the
    * original post on comp.lang.c from Ben B., and Keith T.
    * Ben and Keith gave great insites.
    */

    #include <stdio.h>
    #include <math.h>

    #define LASTNUMBER 1000000 /* change to note the speed diff */
    #define NUMBEROFCOLUMNS 6

    /* prototypes */
    int isThisAPrime ( int number ); /* determines if number is prime */
    int isThisAPrimeWithSqrt (int number ); /* determines if number is prime
    only checking sqrt(number) + 1
    divisible */

    /*********************** main() ********************************/

    int main ( int argc, char *argv[] )
    {
    int total_diff_numbers = 0; /* total of numbers that are different */

    /* 1 not prime by definition */
    for (int number = 2; number < LASTNUMBER; number++ )
    {
    if ( isThisAPrime(number) != isThisAPrimeWithSqrt(number) )
    {
    printf( "%8d\t", number );
    total_diff_numbers++;
    if ( ( total_diff_numbers % NUMBEROFCOLUMNS ) == 0 )
    printf ("\n");

    } /*end if ( isThisA ... ) */

    } /* end for ( int i ... ) */

    printf("\n %d \n\n", total_diff_numbers );
    return 0;

    } /* end main () */


    /*********************** inThisAPrime() *************************/

    int isThisAPrime ( int number )
    {
    if ( number == 2 )
    return 1;
    else
    {
    for ( int i = 2; i < number; i++ )
    {
    if ( (number % i) == 0 )
    return 0;
    }
    } /* end else */

    return 1;

    } /* end isThisAPrime ( int ...) */


    /**** isThisAPrime function with sqrt(number) used ******/

    int isThisAPrimeWithSqrt ( int number )
    {
    int sqRootOfNumber = (int) sqrt(number); /* is used in control loop */
    /* cast to integer */

    if ( number == 2 )
    return 1;
    else
    {
    for ( int i = 2; i < sqRootOfNumber + 1; i++ )
    if ( (number % i) == 0 )
    return 0;

    } /* end else */

    return 1;

    } /* end isThisAPrimeWithSqrt ( int ...) */
     
    G G, Sep 21, 2013
    #6
  7. G G

    G G Guest

     
    G G, Sep 22, 2013
    #7
  8. G G

    G G Guest

    you are absolutely right Keith told me that too.
     
    G G, Sep 22, 2013
    #8
  9. G G

    James Kuyper Guest

    Due to floating point roundoff, that's not necessarily sufficient.
    For sufficiently small squares of integer values, sqrt() is likely to
    return the exact square root, but it's safer not to rely upon that; it's
    certainly not true for larger numbers.
     
    James Kuyper, Sep 22, 2013
    #9
  10. G G

    Eric Sosman Guest

    ... which leads to the Real Way of doing the square-root
    test. If `i' is less than sqrt(number), then `number / i' is
    greater than `i'. And if `i' is greater than sqrt(number), then
    `number / i' is less than `i'. *And* when you ask the computer
    for either of `number % i' or `number / i', the computer almost
    surely calculates the other one as a by-product. *And* a smart
    optimizer will almost certainly notice this, so when it sees both
    `number % i' and `number / i' (for the same `i' and `number'), it
    will very likely perform only one division, retaining both outputs
    instead of discarding one of them.

    Calculating and re-calculating and re-re-calculating sqrt(number)
    is silly to begin with: It'd be better to calculate it once and use
    the calculated root to stop the loop. But even better would be to
    calculate it *never* and use the condition `i / number <= i' to
    stop the loop; it's very probably "free."
     
    Eric Sosman, Sep 22, 2013
    #10
  11. I suppose, but increasing by one isn't all that expensive.
    Since testing one more divisor still should give the right
    result, that is probably what I would do.

    -- glen
     
    glen herrmannsfeldt, Sep 22, 2013
    #11
  12. G G

    Tim Rentsch Guest

    If one is being careful, it's important not to write tests
    this way because of bad results or undefined behavior when
    'number' is very large. For example, on an implementation
    where INT_MAX is 2147483647, suppose the number being tested
    is INT_MAX, which also is prime in this case. When 'i' is
    46340, i*i == 2147395600, which is less than INT_MAX, but
    when 'i' is 46341, i*i == 2147488281, which is an overflow,
    ie, undefined behavior. So to be completely reliable a
    certain amount of care needs to be taken in how the test is
    expressed so it doesn't do the wrong thing in such cases.
     
    Tim Rentsch, Sep 22, 2013
    #12
    1. Advertisements

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.