Abbiamo determinato a livello teorico come crescono i costi di esecuzione in funzione degli input, proveremo ora a confrontare i tempi di esecuzione che si ottengono empiricamente. Occorre sottolineare che questa misura `e soggetta a errori: in genere due diverse misurazioni portano a risultati diversi. Cause tipiche di questo fenomeno sono:
• funzioni di misurazione imprecise (amplificazione degli errori causata da operazioni tra numeri con cifre decimali a precisione finita, limitazioni nella massima precisione delle funzioni usate per calcolare la differenza tra due istanti di tempo, approssimazioni)
• differenze di implementazione (un certo algoritmo implementato in mo- di diversi potrebbe fornire prestazioni diverse da quelle stimate ad alto livello)
• differenze di hardware (uno stesso codice C eseguito su due macchine diverse porter`a probabilmente a tempi di esecuzione diversi)
• altri processi nel sistema operativo (in una stessa macchina sono gene- ralmente in esecuzione multipli processi senza correlazione con quello preso in esame)
I tempi di esecuzione sono per`o un modo estremamente semplice di presen- tare questo genere di dati e renderli confrontabili a ”colpo d’occhio” (pur con una certa approssimazione), senza richiedere all’osservatore conoscenze
specifiche sul tema. Pertanto presentiamo i tempi di esecuzione del program- ma ”ibrido” prodotto in questo lavoro di tesi, confrontandoli con i tempi di esecuzione del metodo ”diretto” nello stesso intervallo15 (i valori in input
sono da considerarsi espressi in base 10). La prima tabella illustra i tempi di esecuzione nel caso in cui l’intervallo `e ”ampio”, tale per cui [A, B] tende all’intervallo massimo [1, B].
A = 1 ⇒ B − A ≈ B
B = 103 B = 104 B = 105 B = 106 Diretto 8ms 0.105s 1.345s 17.240s Ibrido 9ms 0.147s 1.547s 17.781s
La seconda tabella mostra i tempi di esecuzione nel caso di un intervallo pi`u ristretto, tendente al singolo elemento B.
A = B − 1 ⇒ B − A ≈ 0
B = 103 B = 104 B = 105 B = 106 Diretto < 1ms < 1ms < 1ms < 1ms Ibrido 1ms 0.067s 0.457s 3.233s
Interpretiamo ora i risultati. Osservando la seconda tabella rileviamo che, come previsto, per intervalli estremamente ristretti il metodo diretto fornisce prestazioni nettamente superiori. Non sorprende che anche incrementando B di un fattore 103 il tempo di esecuzione appaia costante: data la crescita
logaritmica del costo sarebbe necessario incrementarlo di un fattore ben su- periore prima di iniziare a percepire una differenza nei valori.
Studiando invece i valori corrispondenti nella prima tabella possiamo rilevare che le prestazioni del metodo ibrido sono molto vicine a quelle del metodo diretto quando l’intervallo `e molto vasto (pur rimanendo sempre pi`u lento). Tuttavia notiamo una caratteristica dei tempi di esecuzione che sembra disco- starsi da quanto previsto teoricamente. Abbiamo precedentemente discusso di come il costo di esecuzione del metodo inverso non dipenda dal termine ”A” di input, ma dal solo termine B. Appare dunque curioso come il metodo ibrido (molto simile al metodo inverso) abbia tempi di esecuzione chiara- mente diversi tra la prima e la seconda tabella, pur mantenendo invariato il termine B. Possiamo per`o spiegare molto semplicemente il fenomeno: se la prima fase di costruzione dell’albero `e identica nei due casi (e pertanto con
15Anche per la verifica dell’intervallo con metodo diretto `e stato impiegato lo stesso
programma, ma verificando individualmente ogni valore dell’intervallo e sommando infine i rispettivi tempi di esecuzione. Come gi`a descritto in precedenza, questa implementazione del metodo diretto non usa tecniche per convergere a 1 in un numero di passi inferiore a TST.
tempi pressoch´e equivalenti), la seconda fase di verifica `e molto diversa. Nel caso dell’intervallo di ampiezza minima non occorre molto tempo per scor- rere l’intero intervallo in cerca di numeri da verificare, e similmente saranno molti di meno i numeri che sar`a necessario verificare col metodo diretto (trat- tandosi di un sottoinsieme dell’intervallo pi`u ampio). Dunque il termine in input A influenza i tempi di esecuzione della seconda fase del metodo ibrido, mentre il termine B influenza l’intero programma.
Possiamo soffermarci brevemente su un ultimo punto di riflessione: conside- rato che i valori di B con cui `e stato testato il programma nelle due tabelle non sono abbastanza grandi da rendere accurate le stime probabilistiche, `e molto probabile che l’albero costruito nella prima fase non abbia incontrato tutti i numeri appartenenti alla classificazione ”casi semplici”. Ne consegue che tali numeri saranno stati verificati con il metodo diretto durante la se- conda fase, incrementando ulteriormente la differenza di tempo nel metodo ibrido tra prima e seconda tabella. Incrementando B ulteriormente (a un livello sufficiente da rendere accurate le stime) ci aspettiamo che tutti i ”ca- si semplici” siano verificati in prima fase, lasciando solamente i ”picchi” ed eventuali controesempi nella seconda fase.
In ogni caso i tempi di esecuzione del metodo ibrido con intervallo ampio saranno sempre pi`u alti dei corrispondenti casi con A ≈ B.
Conclusioni
Allo stato attuale16 sono stati verificati tutti i numeri fino a 268 ([12]) e possiamo aspettarci che questo intervallo continuer`a ad essere esteso in fu- turo. Basandoci su questo punto di partenza possiamo dare per scontato che qualunque algoritmo di verifica deve puntare all’efficienza con valori di B estremamente grandi perch´e sia utile alla ricerca. Abbiamo per`o visto che (contrariamente a quanto prevedevamo inizialmente) il metodo inverso e le sue variazioni non sono pi`u efficienti del metodo diretto per grandi intervalli, e anzi tali metodi sono via via meno efficienti al crescere di B. La via dell’al- bero inverso non porter`a a risultati migliori di implementazioni del metodo diretto, anche in considerazione del fatto che entrambe le tipologie di algorit- mo possono essere migliorate in efficienza con il parallelismo e che il metodo inverso ha un consumo di memoria notevolmente superiore a quello diretto (pertanto, avendo a disposizione un tempo di calcolo infinito, il metodo di- retto raggiunger`a il massimo numero verificabile entro i limiti di memoria molto pi`u tardi del metodo inverso).