PROBLEMA Programma in C per trovare numeri di Armstrong

Pubblicità
DispatchCode ha detto:
in realtà... stai facendo comunque il confronto
Clicca per espandere...
ma non faccio ==1 !
DispatchCode ha detto:
A questo punto ho rimosso la pow, implementandola:
Clicca per espandere...
infatti lo sospettavo, l'elevazione a potenza in C impiega un algoritmo che maneggia double e dato che funziona anche coi decimali alla fine sugli interi fa più calcoli del necessario

altre osservazioni, volendo un po' banali ma le faccio lo stesso:
  • il numero 0 non è un numero di Armstrong: è vero che 0^1=0 ma non c'è proprio nella definizione
  • if(num<10) return 1; deve essere la prima istruzione della funzione di test, in modo da risparmiare qualche decimillesimo di picosecondo sui numeri da 1 a 9, dove le prime 4 istruzioni non sono necessarie 😆
  • sempre riguardo alle prime 4 istruzioni proverei a fare una piccola modifica: invece di usare la funzione esterna sprintf, ricaverei l'esponente con un for; il ragionamento di base è il seguente: stiamo usando degli int che sugli attuali sistemi sono numeri a 32 bit, cioè massimo di 10 cifre; quindi un for basato sulla divisione per 10 del numero in input (fino a quando ottieni 0 come risultato) ti ritorna l'esponente, per cui bisogna fare massimo 10 divisioni, a naso il tempo macchina richiesto da 10 divisioni rispetto alla chiamata di una funzione esterna che opera su stringhe dovrebbe essere inferiore; in alternativa un semplice if o switch, una cosa del genere: if(n<100) esponente =2; else if (n<1000) esponente = 3... e così via, anzi più ci penso e più mi convinco che la sequenza di if sia il metodo più rapido
 
Ultima modifica:
BAT ha detto:
ma non faccio ==1 !

infatti lo sospettavo, l'elevazione a potenza in C impiega un algoritmo che maneggia double e dato che funziona anche coi decimali alla fine sugli interi fa più calcoli del necessario

altre osservazioni, volendo un po' banali ma le faccio lo stesso:
  • il numero 0 non è un numero di Armstrong: è vero che 0^1=0 ma non c'è proprio nella definizione
  • if(num<10) return 1; deve essere la prima istruzione della funzione di test, in modo da risparmiare qualche decimillesimo di picosecondo sui numeri da 1 a 9, dove le prime 4 istruzioni non sono necessarie 😆
  • sempre riguardo alle prime 4 istruzioni proverei a fare una piccola modifica: invece di usare la funzione esterna sprintf, ricaverei l'esponente con un for; il ragionamento di base è il seguente: stiamo usando degli int che sugli attuali sistemi sono numeri a 32 bit, cioè massimo di 10 cifre; quindi un for basato sulla divisione per 10 del numero in input (fino a quando ottieni 0 come risultato) ti ritorna l'esponente, per cui bisogna fare massimo 10 divisioni, a naso il tempo macchina richiesto da 10 divisioni rispetto alla chiamata di una funzione esterna che opera su stringhe dovrebbe essere inferiore; in alternativa un semplice if o switch, una cosa del genere: if(n<100) esponente =2; else if (n<1000) esponente = 3... e così via, anzi più ci penso e più mi convinco che la sequenza di if sia il metodo più rapido
Clicca per espandere...

Per il punto 3: il mio suggerimento in un post precedente era proprio utilizzare gli interi invece delle stringhe; i tempi del "mio codice" che ho riportato fanno proprio riferimento a quella versione. 😉

A questo punto faccio che riportare il codice, lo metto sotto spoiler, così se Hero non vuole leggerlo ma ragionarci per conto suo non lo influenzo.

C: 
#include<stdio.h>

inline int my_pow(int n, int e) {
    if(!e) return 1;
    
    int number = n;
    while(--e) {
        number*=n;
    }
    return number;
}

int get_number_of_digit(int number) {
    int digit = 1;
    for(; number/=10; digit++);
    return digit;
}

int sum_pow_digit(int number, int exp) {
    int sum = 0;
    
    do {
        int digit = number % 10;
        sum += my_pow(digit, exp);
    } while(number/=10);
    
    return sum;
}

int is_armstrong(int number) {
    if(!number) {
        return 0;
    }
    
    if(number < 10) {
        return 1;
    }

    int exp = get_number_of_digit(number);
    return sum_pow_digit(number, exp) == number;
}

int main() {
    
    for(int i=0; i<2000000; i++) {
        if(is_armstrong(i))
            printf("%d\n", i);
    }   
    return 0;
}

Ho metto anche inline la funzione my_pow, ma anche togliendolo l'overhead della chiamata rimane trascurabile in realtà (com'è ora è "più efficiente" 😝).
 
DispatchCode ha detto:
Ho metto anche inline la funzione my_pow
Clicca per espandere...
mi fai questa prova?
il mio codice è questo sotto spoiler, c'è qualcosa che non mi torna; ho eseguito il tuo codice (ma sono stato costretto a togliere la parola chiave inline dalla funzione) e l'ho eseguito (intervallo da 1 a 20 milioni), poi ho eseguito il mio e sullo stesso intervallo ci mette quasi un secondo in meno (il mio codice intendo che ci mette meno), il che è spropositato.
Deduco che inline equivalga a fare il calcolo direttamente nella funzione come ho fatto io, ma mi servirebbe la controprova, se me lo esegui col tuo compilatore mi togli la curiosità. Lascia l'intervallo ampio, c'è bisogno di verificare su tempi più lunghi, non preoccuparti che sulla mia vecchia carretta sono poco più di 2 secondi a programma. Mi serve anche a verificare quale metodo sia "meglio" per l'esponente.
Inoltre sarebbe interessante ampliare l'intervallo ancora di più, anche 1 miliardo
Grazie in anticipo
C: 
#include <stdio.h>

int isArmstrongNumber(int n) {
    if(n<10) return 1;
    int e; // esponente
    if(n<100) e = 2;
    else if(n<1000) e = 3;
    else if(n<10000) e = 4;
    else if(n<100000) e = 5;
    else if(n<1000000) e = 6;
    else if(n<10000000) e = 7;
    else if(n<100000000) e = 8;
    else if(n<1000000000) e = 9;
    else e = 10; // perché gli int/unsigned a 32 bit sono a 10 cifre
    int s = 0; // somma
    int n2 = n;
    do {
        int cifra = n2 % 10;
        int p = cifra; // potenza
        for(int i=1; i<e; i++) p *= cifra; // calcola la potenza
        s += p;
        n2 /= 10;
    } while(n2>0);
    return s == n;
}

int main(void) {
    for(int i = 1; i < 20000000; i++)
        if(isArmstrongNumber(i))
            printf("%d\n", i);
    return 0;
}
 
Ultima modifica:
Sono a casa, e ho testato il codice postato da @DispatchCode (quello ottimizzato). Adesso compila senza errori, ma si ferma a 153. Domani, che ho un po' più di tempo libero (oggi ho finito scuola alle 17.40) provo a fare la versione senza stringhe
 
Si, inline fa quanto hai descritto @BAT . Probabilmente si lamenta il compilatore poichè non trova la definizione. Aggiungi int my_pow(int, int); prima della funzione.

L'output del tuo sulla mia macchina impiega:

Codice: 
real    0m1,705s
user    0m1,705s
sys    0m0,000s

Il mio:

Codice: 
real    0m2,464s
user    0m2,463s
sys    0m0,000s

Ma non puntavo a scrivere un codice super performante, più che altro volevo mostrare a Hero un esempio diverso e scritto in maniera leggibile (usando le funzioni).

A questo punto ho rivisto anche il mio codice 🤣 :

C: 
#include<stdio.h>

int my_pow(int n, int e) {  
     int number = n;
    while(--e) {
        number*=n;
    }
    return number;
}

int sum_pow_digit(int number, int exp) {
     int sum = 0;
  
    do {
        int digit = number % 10;
        sum += my_pow(digit, exp);
    } while(number/=10);
  
    return sum;
}

int is_armstrong(int number) {
 
    int exp;
    switch(number) {
        case 0 ... 9:
          return 1;
        case 10 ... 99:
          exp = 2;
        break;
        case 100 ... 999:
          exp = 3;
        break;
        case 1000 ... 9999:
          exp = 4;
        break;
        case 10000 ... 99999:
          exp = 5;
        break;
        case 100000 ... 999999:
          exp = 6;
        break;
        case 1000000 ... 9999999:
          exp = 7;
        break;
        case 10000000 ... 99999999:
          exp = 8;
        break;
        case 100000000 ... 999999999:
          exp = 9;
        break;
        default:
          exp = 10;
    }

    return sum_pow_digit(number, exp) == number;
}

int main() {
  
    for(int i=1; i<20000000; i++) {
        if(is_armstrong(i))
            printf("%d\n", i);
    } 
    return 0;
}

Tempi:
Codice: 
real    0m2,046s
user    0m2,045s
sys    0m0,000s


Se vuoi provarlo però ancor più uttimizzato:

C: 
#include<stdio.h>


int my_pow(int n, int e) {  
    register int number = n;
    while(--e) {
        number*=n;
    }
    return number;
}

int sum_pow_digit(int number, int exp) {
    register int sum = 0;
  
    do {
        int digit = number % 10;
        sum += my_pow(digit, exp);
    } while(number/=10);
  
    return sum;
}

int is_armstrong(int number) {
 
    int exp;
    switch(number) {
        case 0 ... 9:
          return 1;
        case 10 ... 99:
          exp = 2;
        break;
        case 100 ... 999:
          exp = 3;
        break;
        case 1000 ... 9999:
          exp = 4;
        break;
        case 10000 ... 99999:
          exp = 5;
        break;
        case 100000 ... 999999:
          exp = 6;
        break;
        case 1000000 ... 9999999:
          exp = 7;
        break;
        case 10000000 ... 99999999:
          exp = 8;
        break;
        case 100000000 ... 999999999:
          exp = 9;
        break;
        default:
          exp = 10;
    }

    return sum_pow_digit(number, exp) == number;
}

int main() {
  
    for(int i=1; i<20000000; i++) {
        if(is_armstrong(i))
            printf("%d\n", i);
    } 
    return 0;
}

(NOTA: la differenza è sostanzialmente l'utilizzo di register)

Tempi:

Codice: 
real    0m1,678s
user    0m1,677s
sys    0m0,000s

Tutti i codici sono stati compilati senza l'utilizzo di flags.

Sarebbe interessante vedere anche cosa producono altri compilatori di linguaggi come Go e Rust.

Ci sono poi altre inezie ottimizzabili; è interessante ad esempio notare la differenza spostando la divisione da:

C: 
    do {
        int digit = number % 10;
        sum += my_pow(digit, exp);
    } while(number/=10);

a qui:

C: 
    do {
        int digit = number % 10;
        number /= 10;
        sum += my_pow(digit, exp);
    } while(number);

Il tempo passa da quello visto sopra a:
Codice: 
real    0m1,468s
user    0m1,468s
sys    0m0,000s

Non ho guardato se è dovuto all'assembly generato (eg. effettua la divisione solo una volta e poi prende il resto, che tanto si trova in un altro registro della CPU), oppure se è dovuto alla dipendenza o altro ancora.
 
DispatchCode ha detto:
Ma non puntavo a scrivere un codice super performante, più che altro volevo mostrare a Hero un esempio diverso e scritto in maniera leggibile (usando le funzioni).
Clicca per espandere...
👍sì era chiaro, ma ormai stiamo giocando, speremiamo fino all'utlimo bit
DispatchCode ha detto:
Aggiungi int my_pow(int, int); prima della funzione.
Clicca per espandere...
in questo modo funziona, i tempi di esecuzione sono praticamente uguali
DispatchCode ha detto:
(NOTA: la differenza è sostanzialmente l'utilizzo di register)
Clicca per espandere...
2 cose interessanti
  1. l'utilizzo di register: avevo letto su un manuale che è un tipo di direttiva non più necessaria perché ormai i compilatori lo farebbero automaticamente, e invece pare proprio che non sia vero, da quel che sto vedendo mi è bastato aggiungere register alle variabili interne e i tempi di calcolo si sono quasi dimezzati a meno che il contatempo dell'editor mi stia mentendo, ed è il motivo per cui voglio far provare il codice anche a te che hai un PC molto più potente del mio;
  2. la sintassi del case, interessante non sapevo che si potesse fare in quel modo con l'uso di intervalli; a naso e senza averne nessuna prova, secondo me non ti produce codice efficiente quanto una sequenza di if
Dopo cena provo a ricompilare e rieseguire tutto, voglio proprio vedere che esce fuori.

Se ti stai chiedendo perché mi sono fissato sull'ottimizzare questa roba la risposta è che gli interi sono brutte bestie, sto vedendo che questi numeri sono piuttosto rari e quindi anche la più piccola ottimizzazione può tagliare drasticamente i tempi di calcolo quando il controllo viene fatto su decine/centinaia di milioni di numeri
 
@DispatchCode
ho fatto un confronto eseguendo un test con intervallo 1-146511209 (escluso, il numero 146511208 è il 28° n. di Armstrong);
la scelta dell'intervallo allargato serviva a dilatare i tempi di esecuzione.

ho usato l'ultimo codice ottimizzato che mi hai dato, compresa la mini-ottimizzazione sull'ultima divisione, te lo riporto nel caso mi fossi sbagliato, così ricontrolli (sempre se ti va eh)

C: 
#include<stdio.h>

int my_pow(int n, int e) {
    register int number = n;
    while(--e) {
        number*=n;
    }
    return number;
}

int sum_pow_digit(int number, int exp) {
    register int sum = 0;

    do {
        int digit = number % 10;
        number /= 10;
        sum += my_pow(digit, exp);
    } while(number);

    return sum;
}

int is_armstrong(int number) {

    int exp;
    switch(number) {
        case 0 ... 9:
          return 1;
        case 10 ... 99:
          exp = 2;
        break;
        case 100 ... 999:
          exp = 3;
        break;
        case 1000 ... 9999:
          exp = 4;
        break;
        case 10000 ... 99999:
          exp = 5;
        break;
        case 100000 ... 999999:
          exp = 6;
        break;
        case 1000000 ... 9999999:
          exp = 7;
        break;
        case 10000000 ... 99999999:
          exp = 8;
        break;
        case 100000000 ... 999999999:
          exp = 9;
        break;
        default:
          exp = 10;
    }

    return sum_pow_digit(number, exp) == number;
}

int main() {

    for(int i=1; i<146511209; i++) {
        if(is_armstrong(i))
            printf("%d\n", i);
    }
    return 0;
}

Nel mio codice ho aggiunto la keyword register nelle veriabili intere interne alla funzione (erano poche si poteva fare, ovviamente non è una pratica che si possa usare in modo generalizzato); la cosa strana è che dentro l'unico ciclo do-while, sembrerebbe che definire le variabili register (cifra, p) dentro invece che fuoci dal ciclo, migliori leggerissimamente (millisecondi) i tempi di esecuzione; altrettanto avviene nel controllo della condizione: mettere while(n2>0) sembrerebbe "meglio" che mettere while(n2), mah!
C: 
#include <stdio.h>

int isArmstrongNumber(int n) {
    if(n<10) return 1;
    register int e; // esponente
    if(n<100) e = 2;
    else if(n<1000) e = 3;
    else if(n<10000) e = 4;
    else if(n<100000) e = 5;
    else if(n<1000000) e = 6;
    else if(n<10000000) e = 7;
    else if(n<100000000) e = 8;
    else if(n<1000000000) e = 9;
    else e = 10; // perché gli int/unsigned a 32 bit sono a 10 cifre
    register int s = 0; // somma
    register int n2 = n;
    do {
        register int cifra = n2 % 10;
        register int p = cifra; // potenza
        for(register int i=1; i<e; i++) p *= cifra; // calcola la potenza
        s += p;
        n2 /= 10;
    } while(n2>0);
    return s == n;
}

int main(void) {
    for(int i = 1; i < 146511209; i++)
        if(isArmstrongNumber(i))
            printf("%d\n", i);
    return 0;
}

Entrambi i codici producono un risultato corretto EDIT 21/10/22 : purtroppo è un caso, il codice deve essere corretto in quanto riflettendoci, il calcolo delle potenze eccede la magnitudine dei numeri a 32 bit, va cambiato approccio
(ho controllato sui link che dicevo al post precedente: https://oeis.org/A005188/b005188.txt). La differenza sui tempi è piuttosto marcata: col primo codice il miglior risultato ottenuto è stato 16,078 sec. col 2° codice 6,458 sec., quindi è un +148% di tempo del 1° sul 2°. Allargando ulteriormente l'intervallo numerico al 29° e 30° n. di Armstrong la percentuale peggiora
L'impatto di mettere variabili register internamente alla funzione è stato pesantissimo (in senso positivo: ha tagliato il tempo di calcolo), inoltre sospetto che l'overhead di chiamate a funzione non sia trascurabile quando il numero di elementi da controllare cresce.

Ti do' un "compitino": devi tagliare i tempi di calcolo di una decina di volte 😆 tu lo puoi fare perché sicuramente sai come usare il multithreading e la programmazione parallela in C, ecco un'idea di come fare: la funzione di controllo è un unicum, una sola funzione eseguita su una CPU. Quindi, potresti parallelizzare i calcoli lanciando più thread su intervalli distinti, e tenendo conto dell'ultimo intervallo assegnato; per esempio
thread 1 controlla da 1 a 10000
thread 2 controlla da 10001 a 20000
...
thread 8 controlla da 70001 a 80000
- si annota l'intervallo più alto controllato, in questo caso 70001-80000
- quando un thread finisce se ne lancia un altro sull'intervallo successivo, per esempio se il thread 1 finisce per primo esso "muore" e libera risorse, e tu ne approfitti per lanciare un nuovo thread su 80001-90000... (annoti il nuovo massimo intervallo) e così via (OCCHIO: devi mettere un lock sul massimo intervallo altrimenti col multithreading possono essere guai)

Secondo me considerando che hai un 12700K che boosta a 5 GHz dovresti arrivare al numero 912985153 (il 31° di Armstrong in un batter d'occhio: il mio catorcio col codice precedente (non parallelizzato) ci arriva in 40 secondi e spicci, il tuo 12700K con un solo thread dovrebbe metterci circa 5 volte meno (8-9 secondi o meno), se parallelizzi bene ce la fai in meno di 3 secondi
 
Ultima modifica:
Ci provo anch'io:

C: 
#include <stdio.h>

int is_armstrong(unsigned int v[11], unsigned int n)
{
    for(unsigned int i = n; i; n -= v[i % 10], i /= 10);
    return !n;
}

int main()
{
    unsigned int v[11] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    for(unsigned int n = 0; n < 146511209; ++n)
    {
        if(n == v[10])
        {
            for(unsigned int i = 2; i < 11; v[i] *= i, ++i);
        }
        if(is_armstrong(v, n))
        {
            printf("%u\n", n);
        }
    }
    return 0;
}

Ho in mente anche altre idee, ma bisogna vedere se alla fine queste si tramutano in un'ottimizzazione o in un peggioramento... in ogni caso se ne parla domani con calma! 😅
 
Hero467 ha detto:
Mi fa piacere che vi divertiate a competere così, ma lo sapete che non ci sto capendo una mazza, vero?
Clicca per espandere...
non stiamo competendo
se non hai implementato il codice tu stesso, prova a leggere uno dei precedenti, non sono state usate librerie esterne ti deve funzionare per forza

M1n021 ha detto:
bisogna vedere se alla fine queste si tramutano in un'ottimizzazione o in un peggioramento
Clicca per espandere...
dovresti testare i tempi compilando i precedenti codici con la tua macchina e confrontandoli col tuo
non è una gara né a chi vince né a chi scrive codice più criptico/compatto, stiamo solo tentando di abbassare i tempi di calcolo
 
BAT ha detto:
non stiamo competendo
se non hai implementato il codice tu stesso, prova a leggere uno dei precedenti, non sono state usate librerie esterne ti deve funzionare per forza
Clicca per espandere...
Non ho minimamente toccato niente, e ho preso il primo codice ottimizzato da Dispatch, compilava senza errori stavolta. Ho impostato però mille iterazioni, ma mi stampava i numeri di armstrong solo fino al 153, e so per certo che poi ci sono almeno 370 e 371
 
Pubblicità

Ci sono discussioni simili a riguardo, dai un'occhiata!

Pepp91
RISOLTO Programma per rinominare pagine pdf
Risposte
9
Visualizzazioni
576
Pepp91
Pepp91
petrusic
Linguaggio di Programmazione C++ con QT
Risposte
1
Visualizzazioni
577
bigendian
bigendian
manuel_ottani
Migrare a una distro linux pur essendo "dipendente" da programmi esclusivi a Windows, come fare?
Risposte
8
Visualizzazioni
284
manuel_ottani
manuel_ottani
Jeriko73
PROBLEMA Once Human problema trovare amici
Risposte
2
Visualizzazioni
229
Jeriko73
Jeriko73
Pubblicità

Discussioni Simili

Indietro
Top