PROBLEMA Programma in C per trovare numeri di Armstrong

[BAT]

@Hero467 @DispatchCode @Andretti60 @M1n021
mi sono appena accorto che l'approccio seguito da noi tutti porta alla catastrofe: i programmi sono tutti sbagliati anche se restituiscono il risultato corretto. Vanno in overflow, restituiscono il risultato buono solo per pura fortuna

 

[Hero467]

Va be, a questo punto vista la piega presa del topic cambio il titolo

 

[DispatchCode]

@BAT ti rispondo all'ultima parte: si, andranno in overflow per un paio di motivi probabilmente: in primis sull'elevamento a potenza (che facciamo sommando in un ciclo, ma alla fine quello è) e poi sulle somme.
Non era prevista questa "piega", il mio codice ad esempio all'inizio in realtà leggeva solo 1 numero da tastiera e poi faceva il check...

Poi, premessa sul mio Hardware: la mia CPU è un I9 10900kf, ma è sul mio desktop, dove ho Windows.
Il PC che sto utilizzando ora con Ubuntu è un notebook, con un i7-11390H @ 3.40GHz (in generale se compilo codici per Linux sto usando questa macchina).

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;

Si, ho usato sia register che quel tipo di case per fare qualcosa di diverso più che altro (ma su register ero curioso).
Non ti stai sbagliando: register non andrebbe utilizzata, o quantomeno andrebbe utilizzata senza abusarne. Il compilatore fa comunque "quello che vuole", nel senso che può scegliere di ignorare la keywords (può ignorare anche inline, ad esempio).

Di solito il compilatore sa molto meglio cosa fare e come distribuire i pochi registri che ci sono.

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

Visto che stiamo "spremendo" i codici che abbiamo scritto, ho provato con uno switch per confrontarlo alla tua sequenza di if.

Nel tuo caso hai 8 if/elseif (9, con l'else). Ci sarà sicuro della mis-prediction, almeno ogni qual volta cambia il range (e un if diventa "not taken").
Con lo switch sapevo già che GCC avrebbe fatto una porcata senza flag; il codice che produce è infatti questo (non ho disassembler oltre a gdb installati, ho utilizzato Godbolt con GCC):

is_armstrong(int):
        push    rbp
        mov     rbp, rsp
        sub     rsp, 24
        mov     DWORD PTR [rbp-20], edi
        cmp     DWORD PTR [rbp-20], 999999999
        jg      .L9
        cmp     DWORD PTR [rbp-20], 100000000
        jge     .L10
        cmp     DWORD PTR [rbp-20], 99999999
        jg      .L9
        cmp     DWORD PTR [rbp-20], 10000000
        jge     .L11
        cmp     DWORD PTR [rbp-20], 9999999
        jg      .L9
        cmp     DWORD PTR [rbp-20], 1000000
        jge     .L12
        cmp     DWORD PTR [rbp-20], 999999
        jg      .L9
        cmp     DWORD PTR [rbp-20], 100000
        jge     .L13
        cmp     DWORD PTR [rbp-20], 99999
        jg      .L9
        cmp     DWORD PTR [rbp-20], 10000
        jge     .L14
        cmp     DWORD PTR [rbp-20], 9999
        jg      .L9
        cmp     DWORD PTR [rbp-20], 1000
        jge     .L15
        cmp     DWORD PTR [rbp-20], 999
        jg      .L9
        cmp     DWORD PTR [rbp-20], 100
        jge     .L16
        cmp     DWORD PTR [rbp-20], 9
        jg      .L17
        cmp     DWORD PTR [rbp-20], 0
        jns     .L18
        jmp     .L9
.L17:
        mov     eax, DWORD PTR [rbp-20]
        sub     eax, 10
        cmp     eax, 89
        ja      .L9
        jmp     .L22
.L18:
        mov     eax, 1
        jmp     .L20
.L22:
        mov     DWORD PTR [rbp-4], 2
        jmp     .L21
.L16:
        mov     DWORD PTR [rbp-4], 3
        jmp     .L21
.L15:
        mov     DWORD PTR [rbp-4], 4
        jmp     .L21
.L14:
        mov     DWORD PTR [rbp-4], 5
        jmp     .L21
.L13:
        mov     DWORD PTR [rbp-4], 6
        jmp     .L21
.L12:
        mov     DWORD PTR [rbp-4], 7
        jmp     .L21
.L11:
        mov     DWORD PTR [rbp-4], 8
        jmp     .L21
.L10:
        mov     DWORD PTR [rbp-4], 9
        jmp     .L21
.L9:
        mov     DWORD PTR [rbp-4], 10
.L21:
        mov     edx, DWORD PTR [rbp-4]
        mov     eax, DWORD PTR [rbp-20]
        mov     esi, edx
        mov     edi, eax
        call    sum_pow_digit(int, int)
        cmp     DWORD PTR [rbp-20], eax
        sete    al
        movzx   eax, al
.L20:
        leave
        ret

Il che come noti lo rende anche peggio dei tuoi if/elseif.

Visto che stiamo però "spremendo" i codici come dicevo, compiliamo anche ottimizzando, come è giusto fare: io uso -O3.
I tempi relativi agli output sono questi (ho preso gli ultimi codici che hai gentilmente riportato sotto spoiler):

DispatchCode:

real    0m2,843s
user    0m2,843s
sys    0m0,000s

BAT:

real    0m3,462s
user    0m3,458s
sys    0m0,004s

Queseto è il disassembly del tuo codice (se preferisci/preferite, anche su Godbolt, che almeno è colorato: https://godbolt.org/z/csWss3zh3):

isArmstrongNumber:
        mov     eax, 1
        cmp     edi, 9
        jle     .L1
        mov     esi, 2
        cmp     edi, 99
        jg      .L38
.L3:
        mov     r8d, edi
        xor     r9d, r9d
        mov     r10d, 3435973837
        jmp     .L5
.L15:
        mov     r8d, ecx
.L5:
        mov     ecx, r8d
        mov     rax, rcx
        imul    rax, r10
        shr     rax, 35
        lea     edx, [rax+rax*4]
        mov     eax, r8d
        add     edx, edx
        sub     eax, edx
        mov     edx, eax
        imul    edx, eax
        cmp     esi, 2
        je      .L4
        imul    edx, eax
        cmp     esi, 3
        je      .L4
        imul    edx, eax
        cmp     esi, 4
        je      .L4
        imul    edx, eax
        cmp     esi, 5
        je      .L4
        imul    edx, eax
        cmp     esi, 6
        je      .L4
        imul    edx, eax
        cmp     esi, 7
        je      .L4
        imul    edx, eax
        cmp     esi, 8
        je      .L4
        imul    edx, eax
        cmp     esi, 10
        jne     .L4
        imul    edx, eax
.L4:
        imul    rcx, r10
        add     r9d, edx
        shr     rcx, 35
        cmp     r8d, 9
        jg      .L15
        xor     eax, eax
        cmp     edi, r9d
        sete    al
.L1:
        ret
.L38:
        mov     esi, 3
        cmp     edi, 999
        jle     .L3
        mov     esi, 4
        cmp     edi, 9999
        jle     .L3
        mov     esi, 5
        cmp     edi, 99999
        jle     .L3
        mov     esi, 6
        cmp     edi, 999999
        jle     .L3
        mov     esi, 7
        cmp     edi, 9999999
        jle     .L3
        mov     esi, 8
        cmp     edi, 99999999
        jle     .L3
        xor     esi, esi
        cmp     edi, 999999999
        setg    sil
        add     esi, 9
        jmp     .L3
.LC0:
        .string "%d\n"
main:
        push    rbp
        mov     ebp, 1
        push    rbx
        mov     ebx, 3435973837
        sub     rsp, 8
.L47:
        cmp     ebp, 9
        jle     .L75
        mov     esi, 2
        cmp     ebp, 99
        jle     .L42
        mov     esi, 3
        cmp     ebp, 999
        jle     .L42
        mov     esi, 4
        cmp     ebp, 9999
        jle     .L42
        mov     esi, 5
        cmp     ebp, 99999
        jle     .L42
        mov     esi, 6
        cmp     ebp, 999999
        jle     .L42
        mov     esi, 7
        cmp     ebp, 9999999
        jle     .L42
        xor     esi, esi
        cmp     ebp, 99999999
        setg    sil
        add     esi, 8
.L42:
        mov     edi, ebp
        xor     r8d, r8d
        jmp     .L44
.L55:
        mov     edi, ecx
.L44:
        mov     ecx, edi
        mov     rax, rcx
        imul    rax, rbx
        shr     rax, 35
        lea     edx, [rax+rax*4]
        mov     eax, edi
        add     edx, edx
        sub     eax, edx
        mov     edx, eax
        imul    edx, eax
        cmp     esi, 2
        je      .L43
        imul    edx, eax
        cmp     esi, 3
        je      .L43
        imul    edx, eax
        cmp     esi, 4
        je      .L43
        imul    edx, eax
        cmp     esi, 5
        je      .L43
        imul    edx, eax
        cmp     esi, 6
        je      .L43
        imul    edx, eax
        cmp     esi, 7
        je      .L43
        imul    edx, eax
        cmp     esi, 9
        jne     .L43
        imul    edx, eax
.L43:
        imul    rcx, rbx
        add     r8d, edx
        shr     rcx, 35
        cmp     edi, 9
        jg      .L55
        cmp     r8d, ebp
        jne     .L45
        mov     esi, ebp
        mov     edi, OFFSET FLAT:.LC0
        xor     eax, eax
        call    printf
.L45:
        add     ebp, 1
        cmp     ebp, 146511209
        jne     .L47
        add     rsp, 8
        xor     eax, eax
        pop     rbx
        pop     rbp
        ret
.L75:
        mov     esi, ebp
        mov     edi, OFFSET FLAT:.LC0
        xor     eax, eax
        add     ebp, 1
        call    printf
        jmp     .L47

Ci sono cose interessanti, lo sai che potrei scrivere per ore su queste cose
Faccio notare solo alcune cose. I tuoi IF in sequenza sono l'etichetta L38 (lo dico, così tutti possono capire meglio cosa stanno seguendo, anche se non masticano asm):

.L38:
        mov     esi, 3
        cmp     edi, 999
        jle     .L3
        mov     esi, 4
        cmp     edi, 9999
        jle     .L3
        mov     esi, 5
        cmp     edi, 99999
        jle     .L3
        mov     esi, 6
        cmp     edi, 999999
        jle     .L3
        mov     esi, 7
        cmp     edi, 9999999
        jle     .L3
        mov     esi, 8
        cmp     edi, 99999999
        jle     .L3
        xor     esi, esi
        cmp     edi, 999999999
        setg    sil
        add     esi, 9
        jmp     .L3

Faccio notare una cosa interessante, una delle "magie" dei compilatori:

        xor     esi, esi
        cmp     edi, 999999999
        setg    sil
        add     esi, 9

questo è il modo in cui viene gestito l'else del codice di BAT: viene fatto lo XOR di ESI (quindi ESI = 0), viene fatto il compare per capire se EDI (esponente) ha 10 cifre. Questo azzera anche SIL, che è il lower byte di ESI.
Con SETG si evita l'IF, niente branch prediction: SIL viene settato a 1 solo se CMP ha settato nel registro RFLAGS "EDI è più grande di 999999999". A questo punto viene sommato a ESI il valore 9, ottenendo l'esponente presente nell'else, ovvero 10.

E poi @BAT ti faccio notare un'altra cosa interessante di quel codice: il ciclo che moltiplica e che implementa la pow.

        mov     edx, eax
        imul    edx, eax
        cmp     esi, 2
        je      .L43
        imul    edx, eax
        cmp     esi, 3
        je      .L43
        imul    edx, eax
        cmp     esi, 4
        je      .L43
        imul    edx, eax
        cmp     esi, 5
        je      .L43
        imul    edx, eax
        cmp     esi, 6
        je      .L43
        imul    edx, eax
        cmp     esi, 7
        je      .L43
        imul    edx, eax
        cmp     esi, 9
        jne     .L43
        imul    edx, eax

al compilatore non piaceva ed ha capito che visto che può andare da 1 a 10, era meglio fare l'unrolling di quel loop... quindi l'ha srotolato
E in ultimissimo, come viene trasformato quel n2 /= 10:

        imul    rcx, r10
        add     r9d, edx
        shr     rcx, 35

la ADD è da ignorare.
r10 contiene una costante precalcolata, moltiplicata per RCX, che poi viene shiftata a dx 35 volte.

Già che c'ero ho dato uno sguardo al codice di @M1n021 che già a occhio mi sembrava migliore rispetto ai nostri (in quanto è pensata ):

real    0m2,781s
user    0m2,777s
sys    0m0,004s

Compilando con -O3:

real    0m1,069s
user    0m1,069s
sys    0m0,000s

Per dire, il for innestato all'interno dell'if viene tradotto in:

        cmp     ebp, r12d
        jne     .L13
        movdqu  xmm0, XMMWORD PTR [rsp+40]
        movdqu  xmm1, XMMWORD PTR [rsp+40]
        lea     r12d, [rbp+0+rbp*4]
        pmuludq xmm1, XMMWORD PTR .LC4[rip]
        movdqa  xmm2, XMMWORD PTR .LC4[rip]
        pshufd  xmm1, xmm1, 8
        add     r12d, r12d
        psrlq   xmm0, 32
        mov     DWORD PTR [rsp+56], r12d
        psrlq   xmm2, 32
        pmuludq xmm0, xmm2
        movdqu  xmm2, XMMWORD PTR [rsp+24]
        pmuludq xmm2, XMMWORD PTR .LC5[rip]
        pshufd  xmm2, xmm2, 8
        pshufd  xmm0, xmm0, 8
        punpckldq       xmm1, xmm0
        movdqu  xmm0, XMMWORD PTR [rsp+24]
        movups  XMMWORD PTR [rsp+40], xmm1
        psrlq   xmm0, 32
        pmuludq xmm0, XMMWORD PTR [rsp]
        pshufd  xmm0, xmm0, 8
        punpckldq       xmm2, xmm0
        movups  XMMWORD PTR [rsp+24], xmm2
        jmp     .L13

facendo ampio uso di SSE (parallelismo a livello di istruzione).

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

Prendi l'ultima che ha mostrato BAT sotto spoiler (o la mia o la sua, è uguale). Nelle precedenti usavo range diversi.

 

[M1n021]

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

In realtà non mi sembra poi così criptico; riguarda alla compattezza, invece, è semplicemente il mio modo di scrivere codice!

In ogni caso questi i tempi che ottengo con le varie versioni compilate con -O3 (per i vostri codici mi sono riferito a quelli postati sotto spoiler qui):

DispatchCode

Process returned 0 (0x0)   execution time : 7.967 s

BAT

Process returned 0 (0x0)   execution time : 11.414 s

M1n021

Process returned 0 (0x0)   execution time : 3.507 s

Da notare quanto il mio PC sia una carretta rispetto ai vostri (vecchio pentium dual core con 4GB di RAM)!

Tornando al mio codice

#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;
}

provo a spiegare l'idea di fondo.
In pratica, detta c la generica cifra ed e l'esponente, non ha senso calcolare i singoli c^e volta per volta e per ogni numero n da testare; sappiamo infatti che per numeri che hanno lo stesso numero di cifre, i valori di c^e saranno costanti. Quindi nel mio codice mi avvalgo di un array, i cui valori vengono aggiornati soltanto quando n raggiunge una nuova potenza di 10.
Per quanto riguarda la funzione is_armstrong() mi limito semplicemente ad utilizzare la sottrazione al posto dell'addizione.

@Hero467 @DispatchCode @Andretti60 @M1n021
mi sono appena accorto che l'approccio seguito da noi tutti porta alla catastrofe: i programmi sono tutti sbagliati anche se restituiscono i risultati corretto. Vanno in overflow, restituiscono il risultato buono solo per pura fortuna

Perché va in overflow?!

 

[DispatchCode]

In realtà non mi sembra poi così criptico; riguarda alla compattezza, invece, è semplicemente il mio modo di scrivere codice!

E' pensato, c'è dietro un ragionamento; i nostri per capirli è sufficiente leggere il codice, non devi nemmeno ragionarci più di tanto.

Da notare quanto il mio PC sia una carretta rispetto ai vostri (vecchio pentium dual core con 4GB di RAM)!

Si hai tempi nettamente diversi dai miei in effetti. Come li hai misurati? Io ho fatto direttamente time ./programma.

Stasera o post pranzo, se riesco, compilo al volo dal PC fisso usando però MSVC. Vediamo che differenze in termini di tempi ci sono.

 

[BAT]

@Hero467
vediamo se è possibile allinerarci, al di là del fatto che il codice va cambiato ti deve compilare; avrei scritto una miniguida qui, magari se la segui cerchiamo di usare lo stesso compilatore: https://forum.tomshw.it/threads/ins...-e-configurazione-dellide-code-blocks.895158/

@DispatchCode @M1n021
grazie a tutti per l'attenzione, ho scritto il mio catastrofico post perché la faccenda dell'overflow m'è venuta in mente dopo che avevo letto il codice di @M1n021 : non gradisco il codice troppo compatto perché è poco portabile, tuttavia se non l'ho interpretato male, precalcola le potenze in modo da non duplicare i calcoli, è un approccio eccellente. Mentre ci rimuginavo sopra ho spento il PC perché dovevo andare a lavorare, e LAVANDOMI I DENTI (ve lo giuro) m'è venuto in mente il numero 1.999.999.999 9^10 è già fuori dal range dei 32 bit, quindi la somma sarà sbagliata a prescindere, anche se il programma restituisce un risultato giusto lo fa per fortuna.
Quindi non avevo scelta: DOVEVO riaccendere il PC per scrivere quel post (dannazione, odio sbagliare con gli interi!), l'algoritmo in sé è giusto ma l'implementazione C no, Python non pone queto problema perché gli interi sono oggetti ed hanno precisione illimitata (limitata alla macchian sottostante).

In pratica, detta c la generica cifra ed e l'esponente, non ha senso calcolare i singoli c^e volta per volta e per ogni numero n da testare; sappiamo infatti che per numeri che hanno lo stesso numero di cifre, i valori di c^e saranno costanti.

ecco appunto (non avevo ancora letto il tuo post) quindi avevo interpretato bene
questo modo di calcolare taglia un sacco di cicli inutili, bisogna solo aggiustare il tipo della variabile somma per non andar fuori range e dei singoli elementi dell'array, sul mio compilatore gli interi a 64 bit sono long long.
Non ho usato nessun parametro di compilazione particolare, ho lasciato el impostazioni predefinite di GCC 11.2.0 e di CodeBloks.

Sarebbe interessante reimplementare il tutto usando l'approccio di M1n021 , aggiustando i tipi delle variabili e provare l'approccio multithreading per vedere se è possibile tagliare i tempi ancora di più

Perché va in overflow?!

9^10=3.486.784.401‬ eccede il massimo intero in complemento a 2 rappresentabile con 32 bit --> 2^31-1=2.147.483.641‬
l'uso di unisgned non risolve il problema perché qualunque intero a 10 cifre che abbia 2 cifre 9 eccede anche gli unsigned a 32 bit
servono long long o unsigned long long sia per la somma che per le potenze
se usi la sottrazione il discorso è lo stesso

 

[DispatchCode]

range e dei singoli elementi dell'array, sul mio compilatore gli interi a 64 bit sono long long.
Non ho usato nessun parametro di compilazione particolare, ho lasciato el impostazioni predefinite di GCC 11.2.0 e di CodeBloks.

Se si ha come target x86-64 è sufficiente utilizzare long long, in quanto il tipo int è solitamente a 32bit.

Stasera o post pranzo, se riesco, compilo al volo dal PC fisso usando però MSVC. Vediamo che differenze in termini di tempi ci sono.

Niente compilazione al volo, almeno non del mio codice. Mi sono ricordato che MSVC non supporta la sintassi dello switch che ho utilizzato...

Mi sono limitato quindi a provare i vostri, giusto per curiosità, compilando con MSVC (il tempo l'ho preso eseguendo da MSYS):

BAT:

real    0m13.617s
user    0m0.000s
sys     0m0.000s

Con O2

real    0m3.178s
user    0m0.015s
sys     0m0.000s

Quello di M1n021:

real    0m7.252s
user    0m0.000s
sys     0m0.000s

Con O2:

real    0m1.136s
user    0m0.000s
sys     0m0.000s

Sarebbe interessante reimplementare il tutto usando l'approccio di M1n021 , aggiustando i tipi delle variabili e provare l'approccio multithreading per vedere se è possibile tagliare i tempi ancora di più

Penso che con il suo approccio vada scritto un pò diversamente il codice per sfruttare il multithread; non ho molta voglia di dedicarmici e scrivere codice però, lascio a voi/lui il pensiero.
Andrebbe comunque avviato al massimo un numero di thread pari ai core che ha la CPU (meglio se lo si determina dinamicamente, così scala anche senza modificare il sorgente).

Sarebbe anche interessante provare in CUDA C/C++ a questo punto.

 

[BAT]

Penso che con il suo approccio vada scritto un pò diversamente il codice per sfruttare il multithread; non ho molta voglia di dedicarmici e scrivere codice però, lascio a voi/lui il pensiero.

gli stavo giusto "rubando" l'approccio per metterlo in un'unica funzione (per evitare l'appoggio sull'array esterno), vediamo che esce fuori; non userò nessun tipo di ottimizzazione forzata, quindi niente register, solo codice "puro". Non uso neanche particolari opzioni di compilazione, lascerò tutto standard

EDIT
mentre sto codificando mi viene il serio dubbio che il risultato sarà molto meno buono di quel che mi aspettavo all'inizio perché il trasporto dell'array nella funzione comporterà per ogni test il riallocamento dell'array sullo stack e questo farà sprecare un sacco di tempo inutile: più ci penso e più mi convinco che non sarà un buon modo

 

[M1n021]

Si hai tempi nettamente diversi dai miei in effetti. Come li hai misurati? Io ho fatto direttamente time ./programma.

Sono i tempi (comprensivi di output) che restituisce la console. So che non è il metodo migliore, ma è lo stesso che ho utilizzato per tutte e tre le versioni.

Mentre ci rimuginavo sopra ho spento il PC perché dovevo andare a lavorare, e LAVANDOMI I DENTI (ve lo giuro) m'è venuto in mente il numero 1.999.999.999 9^10 è già fuori dal range dei 32 bit, quindi la somma sarà sbagliata a prescindere, anche se il programma restituisce un risultato giusto lo fa per fortuna.
quindi non avevo scelta: DOVEVO riaccendere il PC per scrivere quel post (dannazione, odio sbagliare con gli interi!)

Comunque riferendoci al valore 146.511.209 da te scelto come limite superiore per la ricerca, presumo che la somma più grande sia quella relativa al numero 139.999.999, che è pari a (2.711.963.107), e quindi l'overflow ci sta se si utilizzano interi a 32 bit con segno. Io però ho utilizzato il tipo unsigned, il quale permette di testare tutti i numeri a 9 cifre senza overflow, infatti
somma(999.999.999)=3.486.784.401<4.294.967.295=max(uint32)



Ritornando al problema, avrei anche un'altra idea: detta f() la funzione che per ogni n restituisce la somma delle singole cifre elevate a potenza, è evidente che
f(12334)=f(43321)=f(32431)=...
ossia tra due potenze di 10 consecutive esistono una serie di numeri che sono fra loro "anagrammabili" e di cui risulta quindi superfluo calcolarne più volte la somma.
Con queste premesse il numero minimo di somme da calcolare (intese come chiamate ad f()) dovrebbe essere dato dalle combinazioni con ripetizione C'(m,k) di m elementi (10 nel nostro caso, ossia le cifre 0, 1, 2, 3, 4, 5, 6, 7, 8, 9) di classe k (pari nel nostro caso al numero di cifre considerato).

Essendo
C'(m,k)=(m+k-1)!/[k!(m-1)!]
nel nostro caso la formula si riduce a
C'(10,k)=(9+k)!/[k!(9)!]

Vediamo ora quante somme si "risparmiano" al variare del numero di cifre k; per farlo utilizzo la seguente formula:
C'(10,k)/[10^k-10^(k-1)]
che per un dato k calcola la percentuale di numeri da valutare su quelli totali (il denominatore infatti rappresenta il numero di tutti i possibili numeri a k cifre).

k	%
2	61,111111111%
3	24,444444444%
4	7,944444444%
5	2,224444444%
6	0,556111111%
7	0,127111111%
8	0,027011111%
9	0,005402222%
10	0,001026422%
11	0,000186622%
12	0,000032659%
13	0,000005527%
14	0,000000908%
15	0,000000145%

Come si può vedere il "risparmio" teorico diventa al crescere di k sempre più consistente, bisogna però vedere se, al netto del suo costo computazionale, l'implementazione di questo approccio rappresenta un miglioramento o un peggioramento in termini di tempo d'esecuzione.
Dopo vedo di buttare giù qualche linea di codice...

 

[Hero467]

@Hero467
vediamo se è possibile allinerarci, al di là del fatto che il codice va cambiato ti deve compilare; avrei scritto una miniguida qui, magari se la segui cerchiamo di usare lo stesso compilatore: https://forum.tomshw.it/threads/ins...-e-configurazione-dellide-code-blocks.895158/

C'è un piccolo problema, io uso gcc e ubuntu, e installare code::blocks si sta rivelando più difficile del previsto. Ho scaricato il .den ddel programma, ma non lo installa

 

[BAT]

Comunque riferendoci al valore 146.511.209 da te scelto come limite superiore per la ricerca, presumo che la somma più grande sia quella relativa al numero 139.999.999, che è pari a (2.711.963.107), e quindi l'overflow ci sta se si utilizzano interi a 32 bit con segno. Io però ho utilizzato il tipo unsigned

non va bene in ogni caso, queli limite di ricerca l'ho impostato solo per test per fare più calcoli e allungare i tempi, è proprio l'approccio ad essere sbagliato anche se usi gli unsigned, sempre 32 bit rimangono
se alzi il limite il programma toppa la somma (o la sottrazione) perché non bastano 32 bit, ce ne vogliono 64

intanto ho fatto la prova che anticipavo e portare internamente l'array precalcolato migliora i tempi precedenti ma non abbstanza di quando è esterno, inutile che posto il codice

 

[M1n021]

se alzi il limite il programma toppa la somma (o la sottrazione) perché semplcicemente non bastano 32 bit, c ene vogliono 64

Come dimostrato nel precedente post, con il limite di 146.511.209 non c'è alcun "overflow" con gli uint32, poi è normale che il rischio vada ponderato volta per volta, anche con 64 bit se si alza troppo il tiro si rischia l'overflow!

 

[BAT]

Come dimostrato nel precedente post, con il limite di 146.511.209 non c'è alcun "overflow" con gli uint32, poi è normale che il rischio vada ponderato volta per volta, anche con 64 bit se si alza troppo il tiro si rischia l'overflow!

Ma non va bene un generale, quello era un limite per test,se invece di quello come limite superiore ci metti 2^31-1 i calcoli sono sbagliati. Per tirarti fuori dai guai ti basta usare invece degli unsigned int i long long che sono a 64 bit e sei a posto. In più dovresti usare la somma invece della sottrazione.
L'idea delle permutazioni è interessante ma non è gratis, computazionalmente.

 

[DispatchCode]

C'è un piccolo problema, io uso gcc e ubuntu, e installare code::blocks si sta rivelando più difficile del previsto. Ho scaricato il .den ddel programma, ma non lo installa

Ma non ti serve CodeBlock, utilizza GCC e un qualsiasi editor. Puoi usare VSCode o approfittare del fatto che Jetbrains Fleet sia "public" (free quindi, al momento).

Io quel codice l'ho scritto direttamente su Gedit, tanto sono due righe.

Se invece vuoi proprio codeblocks ed hai scaricato il deb digita:

sudo dpkg -i nome_file.deb

 

[Hero467]

Ma non ti serve CodeBlock, utilizza GCC e un qualsiasi editor. Puoi usare VSCode o approfittare del fatto che Jetbrains Fleet sia "public" (free quindi, al momento).

Davvero l'hanno rilasciato? :O
Mi ero iscritto alla waitlist, ma non mi è arrivata nessuna mail