Optimize spfrhwotimize

Post small pieces of code and optimize each others anus

int is_prime(int num){
    if(num < 1)
        return 0;
    if(num < 3)
        return 1;
    if((num % 2) == 0)
        return 0;
    int i = 3;
    while(num <= i * i){
        if((num % i) == 0)
            return 0;
        i += 2;
    }
    return 1;
}

Time test:

int main(){
    for(int i = 0; i < 10000000; ++i)
        is_prime(i);
    return 0;
}

[code]gcc -O3 prime.c -std=c99
time ./a.out
real    0m0.046s
user    0m0.040s
sys     0m0.000s
[code]

>>1,2,3,4,5
...


Wrote this some time ago.


!@?:~$ gcc -ansi -pedantic -Wall -Wextra -O3 -o eratosthenes eratosthenes.c -lm
eratosthenes.c: In function ‘main’:
eratosthenes.c:5:14: warning: unused parameter ‘argc’ [-Wunused-parameter]
!@?:~$ time ./eratosthenes
./eratosthenes: has 64 bit integer representation; bit-vector size is 156251.
./eratosthenes: took 0.060000 s for calculating all primes below 10000000.

real    0m0.070s
user    0m0.068s
sys    0m0.000s
!@?:~$ gcc -ansi -pedantic -Wall -Wextra -O2 -o eratosthenes eratosthenes.c -lm
...
!@?:~$ time ./eratosthenes
...
./eratosthenes: took 0.050000 s for calculating all primes below 10000000.

real    0m0.056s
user    0m0.052s
sys    0m0.000s
!@?:~$ gcc -ansi -pedantic -Wall -Wextra -O1 -o eratosthenes eratosthenes.c -lm
...
!@?:~$ time ./eratosthenes
...
./eratosthenes: took 0.040000 s for calculating all primes below 10000000.

real    0m0.049s
user    0m0.044s
sys    0m0.000s
!@?:~$ gcc -ansi -pedantic -Wall -Wextra -O0 -o eratosthenes eratosthenes.c -lm
...
!@?:~$ time ./eratosthenes
...
./eratosthenes: took 0.400000 s for calculating all primes below 10000000.

real    0m0.412s
user    0m0.408s
sys    0m0.000s

The code:

eratosthenes.h


unsigned long int *eratosthenes_sieve_l1a(const unsigned long int n);

unsigned long int *eratosthenes_sieve_l1a(const unsigned long int n)
{
    auto unsigned long int *sieve = NULL;
    register unsigned long int i, j, k;
    register const unsigned long int one = 01;
    register const unsigned long int init_int = 0525252525252525252523;
    register const unsigned long int even_int = 0525252525252525252525;
    register const size_t bit_size = sizeof(*sieve)*8;
    register const size_t arr_size = (n/bit_size)+1;
   
    sieve = malloc(sizeof(*sieve)*(((n/bit_size)+1)));
    if (sieve == NULL)
        return NULL;

    *sieve = init_int;
    for (i = 1; i < arr_size; ++i)
        sieve[i] |= even_int;

    /* don't count further than necessary */
    sieve[arr_size-1] &= ((-one) >> (n%bit_size));

    /* the sieve part */
    for (i = 3, j = 0; pow(i,2) <= n; i += 2) {
        j = ((i%bit_size)-1 == 0? j+1 : j);
        if ((j < arr_size) && ((sieve[j] & (one << (i%bit_size))) == 0)) {
            for (k = 2*i; k <= n; k += i)
                sieve[k/bit_size] |= (one << (k%bit_size));
        }
    }

    return sieve;
}

eratosthenes.c


#include <stdio.h>
#include <time.h>
#include "eratosthenes.h"

int main(int argc, char *argv[])
{   
    /*auto short int *sieve = NULL;
    auto long int i, j = 0, n = 1000;*/
    auto unsigned long int *sieve = NULL;
    auto unsigned long int i = 0, j = 0, k = 0, n = 10000000;
    auto const size_t bit_size = sizeof(*sieve)*8;
    auto const size_t arr_size = (((n/bit_size)+1));
    auto clock_t start_t, end_t;

    start_t = (double) clock();
    sieve = eratosthenes_sieve_l1a(n);
    end_t = (double) clock();
   
    if (((int) log(n)) <= 6) {
        while (j < arr_size && i <= n) {
            if ((((*(sieve+j)) & (1UL << i%bit_size))) == 0) {
                printf("%*lu",(int) log(n),i);
                printf("%c",(k%19 != 18? ' ' : '\n'));
                ++k;
            }
            ++i;
            j = ((i%bit_size) == 0? j+1 : j);
        }
        putchar('\n');
    }
   
    /*while (i < n) {
        if (*(sieve+i) == 0) {
            printf("%*li",(int) log(n),i);
            printf("%c",(j%19!=18? ' ' : '\n'));
            ++j;
        }
        ++i;
    }
    putchar('\n');*/
    /*
    for (i = 0; i < arr_size; ++i)
        printf("%*lu ",(int) log(sizeof(unsigned long int)),*(sieve+i));
    putchar('\n');

    for (i = arr_size; (i+1) >= 0; --i)
        printf("%*lu ",(int) log(sizeof(unsigned long int)),*(sieve+i));
    putchar('\n');
    */
   
    printf("%s: %s %lu %s %lu.\n",argv[0],"has",bit_size,
           "bit integer representation; bit-vector size is",
           arr_size);
   
    printf("%s: %s %f s %s %lu.\n",argv[0],"took",
            ((end_t-start_t)/((double) CLOCKS_PER_SEC)),
            "for calculating all primes below",n);
   
    free(sieve);
   
    return 0;
}

I admit, there are some silly things. That malloc() call should not be in the function, but in main() instead. The register constants and the initialization of the vectors should also be in main() (actually the constants could just have been macros with UL at the end). auto is unnecessary, but I like to have the scope of the variables/constants explicit. The stuff commented out were used to pretty print all the primes and the sieve (bit array).

Actually what still annoys me is: ((end_t-start_t)/((double) CLOCKS_PER_SEC)). I read the man pages, further searched and read about time.h, but can't find the cause for why the precision of the execution time is so damn bad.