Calcolo del valore medio senza overflow

Dedicare un post al calcolo della media può sembrare assurdo, ma in realtà gli aspetti ingegneristici che sono dietro l’implementazione di concetti matematici così semplici non sono assolutamente trascurabili. In questo post si vuole mostrare come una soluzione lineare non è sempre la più corretta.

Partiamo dalla definizione di media aritmetica. La media aritmetica è un numero calcolata sommando tutti i valori a disposizione e dividendo il risultato per il numero complessivo dei dati. Per utilizzare un simbolismo matematico:

Media-aritmetica

 Una possibile implementazione in java di una classe che esegue la media aritmetica di N numeri è:

Tutto il lavoro è eseguito dal metodo execute che esegue il ciclo sui valori della lista sommandoli e dividendo il risultato per il numero di elementi. Vediamo ora cosa accade con il semplice Main di test mostrato di seguito:

L’output generato è:

Il primo risultato è corretto mentre il secondo è palesemente sbagliato. Quello che è accaduto è che la somma dei tre valori 2147483647 ha ecceduto il valore massimo rappresentabile con un intero, determinando un overflow che, java ha gestito tornando al valore minimo e proseguendo da questo. In altre parole: Integer.MAX_VALUE + 1 == Integer.MIN_VALUE.

Per ovviare all’inconveniente possiamo progettare una versione dell’algoritmo di media aritmetica più robusto seguendo i seguenti semplici passi “matematici”:

  1. Schermata 2016-07-26 alle 16.17.06
  2. Schermata 2016-07-26 alle 16.18.10
  3. Schermata 2016-07-26 alle 16.18.36
  4. Schermata 2016-07-26 alle 16.19.19
  5. Schermata 2016-07-26 alle 16.20.11

Al passo 5 è evidente che la media di N numeri è calcolabile a partire dalla conoscenza della media dei primi N-1 numeri della sequenza. Questo consente di determinare un algoritmo di calcolo incrementale che non richiede la somma di tutti i valori ma esegue una serie di operazioni parziali che limitano il pericolo di avere overflow. Il codice risultante è:

dove lo stesso metodo di add restituisce la media parziale calcolata sino all’ultimo valore inserito.