OliForum Matematico

Voi che siete esperti, mi sapreste trovare un metodo diretto per il calcolo del massimo comune divisore tra due numeri?

Per metodo diretto intendo un metodo non iterativo (come Euclide) o algoritmico (come il calcolo mediante fattorizzazione dei numeri in questione), ovvero tramite una "semplice" funzione.

Mi scuso in anticipo se il quesito è banale o troppo semplice, ma nonostante i miei sforzi non ho trovato nulla di questo tipo.

khristian ha scritto:Voi che siete esperti, mi sapreste trovare un metodo diretto per il calcolo del massimo comune divisore tra due numeri?

Presuntuoso da parte mia definirmi esperto, ma vabbè... vorrà dire che mi si perdonerà il peccato (del resto comune, da queste parti). La risposta (sarò breve!) è "no". Non che sia noto, almeno... E sinceramente dubito lo sarà mai: l'algoritmo d'Euclide è quanto di meglio si possa chiedere (guardando ai soliti parametri) in termini di routine di calcolo di tipo iterativo (teorema di Lamè). Ogni altra formula non ricorsiva, d'altro canto, non può che fondarsi sulla fattorizzazione. Mi spiace...

Bene o male quindi non ne esiste (ancora) una esplicita. Materia di ricerca quindi.