Perché la modifica di int per accelerare più a lungo l'esecuzione?

Stavo cercando di risolvere i problem #14 from Project Euler, e aveva scritto il seguente C# ...Perché la modifica di int per accelerare più a lungo l'esecuzione?

int maxColl = 0; 
int maxLen = 0; 
for (int i = 2; i < 1000000; i++) { 
    int coll = i; 
    int len = 1; 
    while (coll != 1) { 
    if (coll % 2 == 0) { 
     coll = coll/2; 
    } else { 
     coll = 3 * coll + 1; 
    } 
    len++; 
    } 
    if (len > maxLen) { 
    maxLen = len; 
    maxColl = i; 
    } 
}

Il problema era che, solo corse e corse senza sembrare di fermarsi.

Dopo aver cercato la soluzione di altre persone al problema, ne ho visto uno molto simile, tranne per il fatto che aveva usato molto tempo anziché int. Non ho visto perché questo dovrebbe essere necessario, dal momento che tutti i numeri coinvolti in questo problema sono compresi nell'intervallo di un int, ma l'ho provato comunque.

Cambiando int a long il codice viene eseguito in poco più di 2 secondi.

Chiunque può spiegarmi questo?

fonte

2016-02-09 Avrohom Yisroel

Cambiare semplicemente da int a lungo non dovrebbe rendere questa drammatica differenza. Ho il sospetto che tu abbia un trabocco che impedisce il ciclo di rottura. guardalo nel debugger e vedi se non riesci a capire se c'è un overflow da qualche parte. –

Normalmente Int64 è più lento di Int32. Forse hai qui una gestione di overflow che causa che Int32 è più lento. – Ben

@Ben normalmente è altrettanto veloce, tranne per la divisione e alcune operazioni complesse. Su alcuni sistemi che operano su valori a 32 bit sono ancora più lenti perché è necessario firmare/zero l'estensione e mascherare per convertire in valori a 64 bit –

Quando i uguale 113383, 3X + 1 sequenza ad un certo punto supera il valore massimo di un int, così 3 * coll + 1 overflow e diventa negativo:

113383 → → 340.150 ... → 1.654.740,898 mila → → 827.370.449 -1.812,855948 millions → → -906.427.974 ...

alla fine, la sequenza si snoda nel successivo ciclo di numeri negativi:

... → -17 → -50 → -25 → -74 → -37 → -110 → -55 → -164 → -82 → -41 → -122 → -61 → -182 → -91 → -272 → -136 → -68 → -34 → -17

Questo ciclo non include 1, quindi il ciclo non termina mai.

L'utilizzo di long anziché int garantisce che lo coll non venga mai sovraccaricato.

fonte

2016-02-09 21:23:14

Aargh! Pensavo di averlo controllato. Spiega perché ho avuto problemi simili anche con altre domande. –

I numeri interi sono straripanti e diventano negativi.
Pertanto, il ciclo non termina mai.
Se si avvolge il codice in un blocco checked, verrà visualizzata un'eccezione di overflow.

long è abbastanza grande per memorizzare i valori necessari, in modo che funzioni correttamente.

fonte

2016-02-09 21:21:09 SLaks

grazie per la spiegazione. Il tuo e Michael Liu sono entrati nello stesso momento, e il suo ha avuto un po 'più di spiegazione, quindi lo sto facendo come risposta, ma anche il tuo è stato molto utile. Grazie mille. –

@AvrohomYisroel Per essere onesti, SLaks era due minuti più veloce :) –

Perché la modifica di int per accelerare più a lungo l'esecuzione?

risposta

Problemi correlati