PROBLEMA Programma in C per trovare numeri di Armstrong

[Hero467]

come vuoi
l'importante è farlo bene

Se stai imparando C, usa quello. Ma come dice BAT, come vuoi. Se ti trovi meglio in Python, usa quello, e dopo lo scrivi in C.

Più che altro perché python è un linguaggio che conosco già, ma con il C mi metterei più alla prova. Va be, lo farò in C, però voglio alzare l’asticella: il generatore chiederà all’utente fino a che numero generare, non solo fino a 100. Se non sbaglio esiste una specie di array che ha lunghezza modificabile, giusto?

 

[DispatchCode]

Più che altro perché python è un linguaggio che conosco già, ma con il C mi metterei più alla prova. Va be, lo farò in C, però voglio alzare l’asticella: il generatore chiederà all’utente fino a che numero generare, non solo fino a 100. Se non sbaglio esiste una specie di array che ha lunghezza modificabile, giusto?

Puoi fare due cose, o un VLA, ovvero:

int n;
scanf("%d", &n);

int array[n];

oppure utilizzare malloc/calloc (e ricordati il free quando non usi più quella memoria 😉):

int n;
scanf("%d", &n);

int *array = calloc(n, sizeof(int));

// fai quello che devi....

free(array);

Fatte le dovute premesse, quello che volevo dire è che ho provato a sostituire gli uint64_t con la classe big_int da me implementata, in modo da poter allargare la ricerca fino a K=39. Come prevedibile, a parità di K=18, il programma con i big_int risulta molto più lento, volevo però capire se questa lentezza sia tutta "fisiologica" oppure è dovuta ad una cattiva implementazione della mia classe sui big_int.
A tal proposito volevo chiedere se qualcuno che sia in possesso di una libreria più o meno ufficiale sui big_int potesse testare il suddetto codice, per esempio per K=18, e valutarne il tempo di esecuzione.

Puoi pubblicare il codice che hai scritto? Così vediamo.
Il tuo nuovo codice, compilato con O3, lo eseguo in:

real    0m0,354s
user    0m0,354s
sys    0m0,000s

Utilizza un pò meno il set SSE rispetto alle precedenti versioni; non so se sai di che si tratta, ma nei precedenti codici assembly se noti ci sono XMM0, XMM1... e altri registri analoghi. Fanno parte di SSE, e sono registri a 128bit. Quindi già da qui capirai perchè i tuoi precedenti codici erano così tanto veloci: i nostri sfruttavano 64bit per i calcoli (e 32 le versioni a 32bit), i tuoi 128, quindi venivano calcolati 2 valori alla volta (e nel caso delle variabili a 32bit, nel tuo caso ne venivano calcolati 4).

 

[Hero467]

Ho provato il primo metodo, ma c’è qualche problema, e non avendo modo di fare debug non riesco a risolvere. Non manda nulla in output

#include <stdio.h>

void genPrimes(int *nums) {
    int lenght = sizeof nums / sizeof nums[0];
   
    nums[0] = 0;
   
    for(int i = 0; i < lenght; i++) {     // lo so che qui potrei fare tutto con un unico for, ma era un test
        if(nums[i] % 2 == 0) {
            nums[i] = 0;
        }
    }
   
    for(int i = 0; i < lenght; i++) {
        if(nums[i] % 3 == 0) {
            nums[i] = 0;
        }
    }
   
    for(int i = 0; i < lenght; i++) {
        if(nums[i] % 5 == 0) {
            nums[i] = 0;
        }
    }
   
    for(int i = 0; i < lenght; i++) {
        if(nums[i] % 7 == 0) {
            nums[i] = 0;
        }
    }
   
    for(int i = 0; i < lenght; i++) {
        if(nums[i] != 0) {
            printf("%d\n", nums[i]);
        }
    }
}

int main() {
    int n;
   
    printf("Inserisci fino a che numero devo generare numeri primi: ");
    scanf("%d", &n);
   
    int nums[n];
   
    for(int i = 1; i < n; i++) {
        nums[i - 1] = i;
    }
   
    genPrimes(nums);
}

 

[M1n021]

Il tuo nuovo codice, compilato con O3, lo eseguo in:

real    0m0,354s
user    0m0,354s
sys    0m0,000s

Utilizza un pò meno il set SSE rispetto alle precedenti versioni; non so se sai di che si tratta, ma nei precedenti codici assembly se noti ci sono XMM0, XMM1... e altri registri analoghi. Fanno parte di SSE, e sono registri a 128bit. Quindi già da qui capirai perchè i tuoi precedenti codici erano così tanto veloci: i nostri sfruttavano 64bit per i calcoli (e 32 le versioni a 32bit), i tuoi 128, quindi venivano calcolati 2 valori alla volta (e nel caso delle variabili a 32bit, nel tuo caso ne venivano calcolati 4).

Quindi un pochino più veloce rispetto al precedente (che sul tuo PC richiedeva 0.408s) lo è.
In pratica ho aggiunto un ulteriore elemento all'array v che consente di controllare l'intervallo di appartenenza di sum in questo modo

v[11]<=sum<v[10]

invece che

v[10]/10<=sum<v[10]

No, non conoscevo il set SSE, in ogni caso dalla tua spiegazione credo di aver capito più o meno di cosa si tratta e del perché rende l'esecuzione più veloce. 🙂

Puoi pubblicare il codice che hai scritto? Così vediamo.

Non mi sembra il caso di mettere altra carne sul fuoco in questo topic introducendo una discussione sull'implementazione dei big int! 😅
Per questo chiedevo se qualcuno avesse a disposizione una libreria più o meno "ufficiale" sui big int per testare il codice e valutarne il tempo di esecuzione per K=18, in modo da poter confrontare tale valore con quello ottenuto utilizzando la mia classe sui big int.
Comunque cercando su internet mi sono imbattuto nella seguente libreria che mi sembra di capire sia molto utilizzata ed affidabile: https://gmplib.org/
Il problema è che capire come installarla e utilizzarla richiede un po' di tempo, per questo chiedevo se qualcuno avesse già tutto l'occorrente per effettuare il test.

 

[M1n021]

@Hero467 dico per dire eh, figurati a me non cambia nulla, ma non sarebbe meglio aprire un topic apposito sul crivello di Eratostene? Altrimenti va a finire che il topic diventa troppo confusionario.

 

[Hero467]

Potrebbe essere una buona idea

 

[DispatchCode]

Stavo aspettando di essere al pc per rispondere a entrambi e chiederti @Hero467 di aprire un topic 😉

@M1n021 apri un topic sull'argomento, così possiamo parlarne.

Questo penso abbia raggiunto il suo scopo, possiamo poi anche chiuderlo se Hero non necessita altre dritte sul topic in questione.

 

[Hero467]

No, il programma è fatto e finito. Se riesco provo ad ottimizzarlo, ma si può anche chiudere

 

[DispatchCode]

Va bene, se vuoi ottimizzarlo possiamo anche lasciare aperto, non è un problema, anzi. 😉

Posta pure ciò che hai scritto qui sopra su Eratostene in un altro topic, così ti rispondiamo di là.

 

[M1n021]

@M1n021 apri un topic sull'argomento, così possiamo parlarne.

Devo prima ricontrollare con calma la libreria che ho scritto sui big int e poi lo apro! 🙂