PROBLEMA Programma in C per trovare numeri di Armstrong

[Hero467]

Prima no, ora si. Ma comunque Java vince per un decimo di secondo

 

[BAT]

java è quasi 5 volte più veloce

impossibile, ci deve essere qualcosa che rallenta l'esecuzione
che hardware hai? almeno CPU e RAM

 

[BrutPitt]

Prima no, ora si. Ma comunque Java vince per un decimo di secondo

In C stai usando exponent come int64_t, in java come int ... nella funzione isArmstrong

 

[M1n021]

@M1n021 ci avrei scommesso, davo per scontato non lavorassi come programmatore...

Come mai?


Comunque, riprendendo l'ultimo codice che ho postato, ho fatto alcune piccole ottimizzazioni e alcune piccole modifiche per fare in modo che anche lo zero sia conteggiato come numero di Armstrong (non vedo perché escluderlo ):

#include <stdio.h>
#include <inttypes.h>

#define K 18 //MAX 18

int combinazione_R_successiva(unsigned int *u, const unsigned int n, const unsigned int k)
{
    for(unsigned int i = k - 1; i < k; --i)
    {
        if(u[i] < n - 1)
        {
            if(++u[i] != n - 1)
            {
                for(unsigned int j = i + 1; j < k; u[j++] = u[i]);
            }
            return 1;
        }
    }
    return 0;
}

int is_armstrong(unsigned int *u, uint64_t *v, const unsigned int k, uint64_t *sum)
{
    unsigned int w[10] = {0};
    unsigned int i;
    for(i = 0; i < k; *sum += v[u[i]], ++w[u[i++]]);
    if(*sum >= v[11] && *sum < v[10])
    {
        for(uint64_t temp = *sum; w[temp % 10]--; temp /= 10, --i);
    }
    return !i;
}

int main()
{
    uint64_t v[12] = {0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
    for(unsigned int cont = 0, k = 1; k <= K; ++k)
    {
        if(k != 1)
        {
            v[11] = v[10];
        }
        for(uint64_t i = 2; i < 11; v[i] *= i, ++i);
        unsigned int u[K] = {0};
        do
        {
            uint64_t sum = 0;
            if(is_armstrong(u, v, k, &sum))
            {
                printf(" %2u: %"PRIu64"\n", ++cont, sum);
            }
        }
        while(combinazione_R_successiva(u, 10, k));
    }
    return 0;
}

Ho provato anche a sostituire il seguente for:

for(uint64_t temp = *sum; w[temp % 10]--; temp /= 10, --i);

con

for(lldiv_t d = {*sum}; w[(d = lldiv(d.quot, 10)).rem]--; --i);

ma è più lento.

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.

 

[Hero467]

In C stai usando exponent come int64_t, in java come int ... nella funzione isArmstrong

Sistemato, C guadagna due decimi di secondo che lo fanno vincere.

Ma comunque, cosa serve effettivamente il flag -O3?

 

[BrutPitt]

Sistemato, C guadagna due decimi di secondo che lo fanno vincere.

Ma comunque, cosa serve effettivamente il flag -O3?

-O2, -O3 (etc.) sono i vari livelli di ottimizzazione del codice prodotto dal compilatore gcc, di seguito li hai tutti:

Optimize Options (Using the GNU Compiler Collection (GCC))

Optimize Options (Using the GNU Compiler Collection (GCC))

gcc.gnu.org

... per default l'opzione e' -O0

 

[Hero467]

Ma perché gcc non compila direttamente in O3? Che senso ha non usare il livello pi§ alto di ottimizzazione

 

[BrutPitt]

Ma perché gcc non compila direttamente in O3? Che senso ha non usare il livello pi§ alto di ottimizzazione

Perche' con meno ottimizzazioni il tempo di compilazione si riduce (pensa a progetti piu' grandi)... quando hai definitivamente "sistemato" il codice, rilasci la tua release, con il livello di ottimizzazione desiderato.
Ed anche se devi fare debug... non e' indicata l'ottimizzazione
E puoi anche decidere di ottimizzare per "size" (dimensione eseguibile) per esempio

 

[BAT]

Sistemato, C guadagna due decimi di secondo che lo fanno vincere.

Ma comunque, cosa serve effettivamente il flag -O3?

comunque, anche per colpa nostra (mia prima di tutto) stai perdendo d'occhio il vero obiettivo, che è imparare a programmare bene (si spera);
non focalizzarti sulle prestazioni, è sbagliato, focalizzati sull'algoritmo;
la funzione isArmstrong() deve restituire vero/falso, se lo fa velcocemente tanto meglio; una funzione che risponde si/no raramente è adatta per generare numeri di un certo tipo, si usano i crivelli come ha fatto il nostro amico @M1n021
ti faccio un altro esempio: se programmi una funzione che testa se un numero è primo, non è conveniente usarla per generre intervalli di numeri primi

Come mai?

perchè il codice che hai scritto è poco modulare
usando un crivello la funzione isArmstrong ha un nome sbagliato (dovresti chiamarla generaArmstrong) perché non ritorna 0/1 o true/false, quindi non è riutilizzabile a quello scopo
poi la funzione stessa usa un array su cui un ciclo for esterno (che non fa parte della funzione) fa side-effetct su un array
insomma il problema è risolto brillantemente, volendoci perdere tempo potresti aggiustare un po' il codice, in prestazioni ci perdi veramente poco

 

[Hero467]

comunque, anche per colpa nostra (mia prima di tutto) stai perdendo d'occhio il vero obiettivo, che è imparare a programmare bene (si spera);
non focalizzarti sulle prestazioni, è sbagliato, focalizzati sull'algoritmo;
la funzione isArmstrong() deve restituire vero/falso, se lo fa velcocemente tanto meglio; una funzione che risponde si/no raramente è adatta per generare numeri di un certo tipo, si usano i crivelli come ha fatto il nostro amico @M1n021
ti faccio un altro esempio: se programmi una funzione che testa se un numero è primo, non è conveniente usarla per generre intervalli di numeri primi

Io però non ho la minima idea di come fare un crivello del genere. E mi stupisco anche di essere riuscito a mettere insieme nu programma simile (in C), ovviamente con i dovuti aggiustamenti da parte vostra

Perche' con meno ottimizzazioni il tempo di compilazione si riduce (pensa a progetti piu' grandi)... quando hai definitivamente "sistemato" il codice, rilasci la tua release, con il livello di ottimizzazione desiderato.
Ed anche se devi fare debug... non e' indicata l'ottimizzazione
E puoi anche decidere di ottimizzare per "size" (dimensione eseguibile) per esempio

Ah, ha senso

 

[BAT]

Io però non ho la minima idea di come fare un crivello del genere

non ce l'hai ancora perché l'Informatica, guarda caso, è la scienza che studia gli algoritmi: sono cose che si studiano piano piano. Ma un crivello per i numeri primi puoi già programmarlo anche tu, si chiama Crivello di Eratostene e puoi farlo perfino a mano per piccoli intervalli di numeri ovviamente
fai una tabella come quella delle tabelline e ci scrivi i numeri da 1 a 100
dato che 2 è il primo numero primo, cancelli il numero uno e tutti i numeri pari eccetto il 2 (al 2 fai un cerchietto)
il primo numero NON cancellato dopo il 2 è il numero 3: gli fai un cerchietto e poi cancellli tutti i numeri multipli di 3 (6, 9, 12...)
il successivo numero non cancellato è il 5, gli fai un cerchietto e poi cancelli i multipli di 5 (10,15,20...)
e continui così fino a quando arrivi alla fine della tabella con solo cerchietti (i numeri primi) o numeri cancellati (che non sono primi)
fallo a mano per bene e troverai la sequenza 2,3,5,7,11,13,17.... tutti i numeri primi minori di 100
poi lo fai al computer: ti basta un array di 100 posizioni provaci, vedrai che ti diverti

 

[Hero467]

non ce l'hai ancora perché l'Informatica, guarda caso, è la scienza che studia gli algoritmi: sono cose che si studiano piano piano. Ma un crivello per i numeri primi puoi già programmarlo anche tu, si chiama Crivello di Eratostene e puoi farlo perfino a mano per piccoli intervalli di numeri ovviamente
fai una tabella come quella delle tabelline e ci scrivi i numeri da 1 a 100
dato che 2 è il primo numero primo, cancelli il numero uno e tutti i numeri pari eccetto il 2 (al 2 fai un cerchietto)
il primo numero NON cancellato dopo il 2 è il numero 3: gli fai un cerchietto e poi cancellli tutti i numeri multipli di 3 (6, 9, 12...)
il successivo numero non cancellato è il 5, gli fai un cerchietto e poi cancelli i multipli di 5 (10,15,20...)
e continui così fino a quando arrivi alla fine della tabella con solo cerchietti (i numeri primi) o numeri cancellati (che non sono primi)
fallo a mono per bene e troverai la sequenza 2,3,5,7,11,13,17.... tutti i numeri primi minori di 100
poi lo fai al computer: ti basta un array di 100 posizioni provaci, vedrai che ti diverti

Mi ricordo quando lo facevo alle elementari. Lo faccio in C o in python?

 

[BAT]

Mi ricordo quando lo facevo alle elementari. Lo faccio in C o in python?

come vuoi
l'importante è farlo bene

 

[DispatchCode]

Mi ricordo quando lo facevo alle elementari. Lo faccio in C o in python?

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.

Come mai?

Domani leggo bene tutto il post, sono da smartphone.
Comunque l'ho detto perché se sviluppi gestionali, CMS o software di questo tipo, o comunque se non lavori creando applicazioni particolarmente complesse, il problema medio che ti trovi a risolvere richiede anche meno "sforzo mentale" di quello che hai usato tu. E con il passare del tempo sei anche "meno allenato" nel pensare a cose più complesse (personalmente ho trascorso 4 anni così, e... lasciamo perdere, pessima scelta da parte mia).

Sistemato, C guadagna due decimi di secondo che lo fanno vincere.

Ma comunque, cosa serve effettivamente il flag -O3?

-O2, -O3 (etc.) sono i vari livelli di ottimizzazione del codice prodotto dal compilatore gcc, di seguito li hai tutti:

Optimize Options (Using the GNU Compiler Collection (GCC))

Optimize Options (Using the GNU Compiler Collection (GCC))

gcc.gnu.org

... per default l'opzione e' -O0

Non sono particolarmente stupito per le performance di Java visto che usa JIT: C1 e C2 (Hotspot, che usa prima C1 e poi C2 per le funzioni più richiamate)

 

[Andretti60]

… piccole modifiche per fare in modo che anche lo zero sia conteggiato come numero di Armstrong (non vedo perché escluderlo ):

Dipende che insieme di numeri si considera, e come tale insieme viene definito.
Nel nostro caso parliamo di numeri naturali (l’insieme N), che può essere definito sia come “interi positivi” (per cui lo zero è escluso) o come “non negativi” (nel quale caso lo zero è incluso). Dipende dal contesto che si sta studiando, anche se ultimamente si preferisce includere lo zero. Nel nostro caso, non ha proprio importanza.