b'\n_START_ARTICLE_\nAlgoritmo di Euclide\n_START_PARAGRAPH_\nL\'algoritmo di Euclide \xc3\xa8 un algoritmo per trovare il massimo comune divisore (indicato di seguito con MCD) tra due numeri interi. \xc3\x88 uno degli algoritmi pi\xc3\xb9 antichi conosciuti, essendo presente negli Elementi di Euclide intorno al 300 a.C.; tuttavia, probabilmente l\'algoritmo non \xc3\xa8 stato scoperto da Euclide, ma potrebbe essere stato conosciuto anche 200 anni prima. Certamente era conosciuto da Eudosso di Cnido intorno al 375 a.C.; Aristotele (intorno al 330 a.C.) ne ha fatto cenno ne I topici, 158b, 29-35. L\'algoritmo non richiede la fattorizzazione dei due interi._NEWLINE_Dati due numeri naturali a e b, si controlla se b \xc3\xa8 zero (questa prima fase rientra ovviamente nell\'ambito di un uso moderno dell\'algoritmo ed era ignorata da Euclide e dai suoi predecessori, che non conoscevano lo zero). Se lo \xc3\xa8, a \xc3\xa8 il MCD. Se non lo \xc3\xa8, si_NEWLINE_divide a / b e si assegna ad r il resto della divisione (operazione indicata con "a modulo b" pi\xc3\xb9 sotto). Se r = 0 allora si pu\xc3\xb2 terminare affermando che b \xc3\xa8 il MCD cercato, altrimenti occorre assegnare a = b e b = r e si ripete nuovamente la divisione._NEWLINE_L\'algoritmo pu\xc3\xb2 essere anche espresso in modo naturale utilizzando la ricorsione in coda._NEWLINE_Tenendo nota dei quozienti ottenuti durante lo svolgimento dell\'algoritmo, si possono determinare due interi p e q tali che ap\xc2\xa0+\xc2\xa0bq\xc2\xa0=\xc2\xa0MCD(a,\xc2\xa0b)._NEWLINE_Questo \xc3\xa8 noto con il nome di algoritmo di Euclide esteso._NEWLINE_Questi algoritmi possono essere usati, oltre che con i numeri interi, in ogni contesto in cui \xc3\xa8 possibile eseguire la divisione col resto. Ad esempio, l\'algoritmo funziona per i polinomi ad una indeterminata su un campo K, o polinomi omogenei a due indeterminate su un campo, o gli interi gaussiani. Un oggetto algebrico in cui \xc3\xa8 possibile eseguire la divisione col resto \xc3\xa8 chiamato anello euclideo._NEWLINE_Euclide originariamente formul\xc3\xb2 il problema geometricamente, per trovare una "misura" comune per la lunghezza di due segmenti, e il suo algoritmo procedeva sottraendo ripetutamente il pi\xc3\xb9 corto dal pi\xc3\xb9 lungo. Questo procedimento \xc3\xa8 equivalente alla implementazione seguente, che \xc3\xa8 molto meno efficiente del metodo indicato sopra:\n_START_SECTION_\nDimostrazione della correttezza dell\'algoritmo\n_START_PARAGRAPH_\nSiano a e b interi positivi assegnati, e sia d il loro MCD._NEWLINE_Definiamo la successione di ricorrenza corrispondente ai passi dell\'algoritmo di Euclide: a\xe2\x82\x80 = a, b\xe2\x82\x80 = b, a\xe2\x82\x99\xe2\x82\x8a\xe2\x82\x81=b\xe2\x82\x99, e b\xe2\x82\x99\xe2\x82\x8a\xe2\x82\x81 \xc3\xa8 il resto della divisione di a\xe2\x82\x99 per b\xe2\x82\x99, cio\xc3\xa8 a\xe2\x82\x99 = q\xe2\x82\x99b\xe2\x82\x99 + b\xe2\x82\x99\xe2\x82\x8a\xe2\x82\x81._NEWLINE_Per definizione di resto nella divisione, b\xe2\x82\x99\xe2\x82\x8a\xe2\x82\x81 < b\xe2\x82\x99 per ogni n, quindi la successione dei b\xe2\x82\x99 \xc3\xa8 strettamente decrescente, e quindi esiste un N tale che bN = 0._NEWLINE_Vogliamo dimostrare che d = aN._NEWLINE_Infatti, per induzione si ha per ogni n che d | a\xe2\x82\x99 = b\xe2\x82\x99\xe2\x82\x8b\xe2\x82\x81 = a\xe2\x82\x99\xe2\x82\x8b\xe2\x82\x82 - q\xe2\x82\x99\xe2\x82\x8b\xe2\x82\x82b\xe2\x82\x99\xe2\x82\x8b\xe2\x82\x82. Inoltre, sempre per induzione, aN divide a\xe2\x82\x99 per ogni n \xe2\x89\xa4 N, quindi divide anche b\xe2\x82\x99 per ogni n < N, quindi aN = d.\n_START_SECTION_\nTempo di calcolo\n_START_PARAGRAPH_\nQuando si analizza il tempo di calcolo dell\'algoritmo di Euclide, si trova che i valori di input che richiedono il maggior numero di divisioni sono due successivi numeri di Fibonacci, e il caso peggiore richiede O(n) divisioni, dove n \xc3\xa8 il numero di cifre nell\'input. Occorre anche notare che le divisioni non sono operazioni atomiche (se i numeri sono pi\xc3\xb9 grandi della dimensione naturale delle operazioni aritmetiche del computer), visto che la dimensione degli operandi pu\xc3\xb2 essere di n cifre. Allora il tempo di calcolo reale \xc3\xa8 quindi O(n\xc2\xb2)._NEWLINE_Questo tempo \xc3\xa8 comunque considerevolmente migliore rispetto all\'algoritmo euclideo originale, in cui l\'operazione di modulo \xc3\xa8 effettuata mediante ripetute sottrazioni in O(2\xe2\x81\xbf) passi. Di conseguenza, questa versione dell\'algoritmo richiede un tempo pari a O(n2\xe2\x81\xbf) per numeri con n cifre, o O(mlog m) per il numero m._NEWLINE_L\'algoritmo di Euclide \xc3\xa8 ampiamente usato nella pratica, specialmente per numeri piccoli, grazie alla sua semplicit\xc3\xa0. Un algoritmo alternativo, l\'algoritmo del MCD binario, utilizza la rappresentazione binaria dei computer per evitare le divisioni e quindi aumentare l\'efficienza, sebbene anch\'esso sia dell\'ordine di O(n\xc2\xb2): infatti su molte macchine reali permette di diminuire le costanti nascoste nella notazione "O grande".'