Eventuali problemi di moltiplicazione con potenziale overflow e quindi verifica con divisione?

Question

Supponiamo di avere due variabili size_t e ho bisogno di moltiplicarle e ottenere il risultato come size_t.

size_t first = ...; 
size_t second = ...; 
size_t result = first * second; 

Potrebbero traboccare quindi ho bisogno di controllare per quello.

Il modo "pulito" sarebbe di controllare in primo che la moltiplicazione è possibile utilizzando divisione:

if(second != 0 && first > ((size_t)-1)/second) { 
    //handle overflow 
} 
//proceed with computing first * second 

Il modo apparentemente meno "pulito" è moltiplicare e poi controllare il risultato con divisione:

Tuttavia, poiché la moltiplicazione di numeri non firmati "overflow in modo sicuro" avvolgendo intorno allo zero, funziona perfettamente e sembra equivalente al codice precedente (che prima controlla, quindi moltiplica).

Ci sono potenziali problemi con il secondo codice? Sarà sempre buono come il primo?

Answer 1

Da un POV matematico, se

((a*b) mod (2^n))/b == a 

è vero per alcuni valori traboccante (questo implica una e b entrambi non 0), allora E''s un problema.
Per raggiungere Wolfram Alpha, non è mai vero per overflow perché per ottenere un risultato, la lunghezza di bit
della variabile risultato n deve essere maggiore della lunghezza bit necessaria di a * b (log[2](a*b)).

Per quanto riguarda il codice, non riesco a pensare a nessun problema neanche ora.

Answer 2

direi che non solo è necessario controllare la divisione, ma si dovrebbe anche controllare il resto troppo:

if(second != 0 && (result/second != first || (result % second) != 0)) 

Se c = b * a, allora c'è solo una valore di c come c/b = a. Cercare di dividere qualsiasi altro valore con b non produrrà a.

Tuttavia non si tratta di matematica intera, ma di vera matematica. Poiché la divisione in interi termina, la formula non sarà tecnicamente vera, poiché, a condizione che b sia almeno 2, (c + 1)/b sarebbe anche a, per alcuni valori di c.

Answer 3

Il primo metodo che si punta sopra è definitivamente errato. La trasmissione di un numero negativo a un tipo senza segno non è corretta come sopra e si riferisce al comportamento non definito.

Il secondo metodo, in quanto l'unico modo in cui un prodotto può essere diverso dalla moltiplicazione di due fattori è avere un overflow nel mezzo, sarebbe corretto, ma ancora una volta, l'overflow può occuparsi del comportamento non definito e in quanto tale, sarebbe non corretto (stai implicitamente pensando che l'overflow deriverà da un'operazione di moltiplicazione modulo, e il risultato in effetti non è definito).

Un modo per verificare la presenza di eventuale troppo pieno potrebbe essere:

if (MAX_UINT/one_of_the_factors < the_other_factor) ... 

Questo è completamente definito e consentono di rilevare l'overflow prima di fare la moltiplicazione reale in un modo portabile.