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]

int is_prime(int num){
  return PRIME[num];
}

where PRIME[] is a bit array representing all prime numbers less than 10000000

If you're going to be checking that many numbers there's no reason to do the same math over and over again.

http://dis.4chan.org/read/prog/1188931649

int is_prime(int num)
{
    for (int i = 0; i < num; i++)
    {
        for (int x = 0; x < num; x++)
        {
            for (int a = 0; a < num; a++)
            {
                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;
            }
        }
    }
}

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

optimized

>>2

First you have to initialize that array.

ITT CS101

>>5
It's declared outside of the function, so it's already initialized. I just didn't show it for brevity's sake.

This still technically doesn't work because it returns a bit rather than an int, but you should get the general idea.

>>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.

gcc

g++

>>8
But that's slower than >>1

>>8
Using some same assumptions (no negative numbers, no even numbers, start from 3)
int main(){
    int total_primes = 3;
    for(int num = 5; num <= 10000000; num += 2){
        int i = 3;
        while(num <= i * i){
            if((num % i) == 0){
                --total_primes;
                break;
            }
            i += 2;
        }
        ++total_primes;
    }
}

real    0m0.010s
user    0m0.012s
sys     0m0.000s

-std=c99
ISHIGIDDY~

>>8
FrozenVoid? Is that you?

>>14
Not him. He never paid much attention to proper formatting.


int main()
{
    return 0;
}

gcc -O3 prime.c -std=c99

閗匢䔁䒐蚅䁁␲啖愧鍓㔘㝖㆒硑╤鍱❸焃䔆萣历ࡲ᝱肆ᔧ鑓㎘❶唖瘡┰E適饦锄│噀ሗ⎀剈愐⤰舨䜃ၘ锳ₑݠ‒慁ᙴ║∇䚄馃莗蚙ጔ搨ኒ閒䉃኉䐳獖䆂聙㑕眣≘蒔呵⌀葀砠锲⥣㙹≗捲ጷ隖䎁ቸᥧ儠ࠕ鎉唙䉴∁䙦☰ㅴ䈢灠㦑酘萸煸別耴焉❒硅㝉⚇ᄁ>鐁禓䢒充㞘阀؇聹㌥肕㝹呃ॴ㝓褧攒اə䢕灠ፃ%脅礧蔗䝔ᢒ堶ሡ᥀剰Ԡ䌔اЦ唇瑹╓椂䙧б䡠أ艡吒䡢ݧ䕠䅘覀呵爖䆖咐術扙ኁ靇昱嚅㘁卥钗暃㥳∴⒀⤁့咀覆䐠፵聇᝔䝘ٔ犅戢袐Ȁᡧ鈰䞐镖脅葄恡᠀圥隖Ĵㄧᤓ睇≠䂒抗蘢Փႅ煶֕恹瞑Ґ㤴ဥᐔ戰慓⎒ᕵķ鉔မ䕓斔榈䢐呙锅䔨餔ܡᙳ砖≩琤戵ᔧ␕҂慧瀥肀Љ怦墘蕇蝲䊆䘠ė奄ᐤ䈧ㅰ䐖Җ慱⡳斆ᄑ२ᑖ瘶ቆ䠧䌡鄐҄ᎀ願焱猆炑犄祖〙ℑ㝃䑷ㅱᘀ杦䎆朗㘒蝤⠆ȡ⠁㘤奰晱牁吂䔩到