A proposito del Massimo Comune Divisore.

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
khristian
Messaggi: 46
Iscritto il: 01 gen 1970, 01:00
Località: Trieste

A proposito del Massimo Comune Divisore.

Messaggio da khristian » 10 ott 2005, 16:36

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.

khristian
Messaggi: 46
Iscritto il: 01 gen 1970, 01:00
Località: Trieste

Messaggio da khristian » 10 ott 2005, 16:36

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

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Re: A proposito del Massimo Comune Divisore.

Messaggio da HiTLeuLeR » 10 ott 2005, 18:35

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... :cry:

khristian
Messaggi: 46
Iscritto il: 01 gen 1970, 01:00
Località: Trieste

Messaggio da khristian » 10 ott 2005, 19:42

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

Rispondi