Algoritmo di Lepore per il calcolo del MCD
Risposte
Praticamente stai dicendo una cosa ovvia, cioè che il MCD tra $6A+1$ e $6B+1$ divide $(6A+1)-(6B+1) = 6(A-B)$, quindi MCD divide $A-B$ se MCD è coprimo con $6$. Tutto il resto ho paura che siano chiacchiere.
Ti consiglio di usare l'algoritmo di Euclide per il calcolo dell'MCD.
Ti consiglio di usare l'algoritmo di Euclide per il calcolo dell'MCD.
Ma se questo è più veloce perchè usare Euclide?
ti consiglio di dare un'occhiata alla prima definizione qui http://www.albericolepore.org/definizio ... strazioni/
ti consiglio di dare un'occhiata alla prima definizione qui http://www.albericolepore.org/definizio ... strazioni/
Non è più veloce. Euclide è più veloce. Ciao
ciao.
se provi con un esempio vedrai che forse ti sbagli.
se provi con un esempio vedrai che forse ti sbagli.
Ciao ragazzi ho provato a scrivere un algoritmo per il calcolo del MCD che è molto migliorabile.
Erano più di 10 anni che non scrivevo codice.
Potreste darmi un parere.
Ho fatto un mix Euclide Lepore
Erano più di 10 anni che non scrivevo codice.
Potreste darmi un parere.
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int main()
{
int valMCD=1;
int a=0;
int b=0;
int rip=1;
int i=0;
int j=0;
int k=0;
int e=0;
printf("Inserisci il primo numero\n");
scanf("%d",&a);
printf("Inserisci il secondo numero\n");
scanf("%d",&b);
while(a % 2 == 0){ a=a/2; i++;}
while(a % 3 == 0){ a=a/3; j++;}
while(b % 2 == 0){ b=b/2; k++;}
while(b % 3 == 0) {b=b/3; e++;}
if ((i!=0 && k!=0)&&(i>=k)) {
rip=rip*pow(2,k);
}else if ((i!=0 && k!=0)&&(i<=k)){
rip=rip*pow(2,i);
}
if ((j!=0 && e!=0)&&(j>=e)) {
rip=rip*pow(3,e);
}else if ((j!=0 && e!=0)&&(j<=e)){
rip=rip*pow(3,j);
}
valMCD=(MCD(a,b))*rip;
printf("valMCD=%d",valMCD);
}
int MCD(a,b){
printf("a=%d\nb=%d\n",a,b);
int c=0;
int d=0;
while(a % 2 == 0){ a=a/2; }
while(a % 3 == 0){ a=a/3; }
while(b % 2 == 0){ b=b/2; }
while(b % 3 == 0) {b=b/3; }
if( (a % b)==0){
return b;
}else if ((b % a)==0){
return a;
}
if ((((a % 6)==1) && ((b % 6)==5) )|| ((a % 6)==5 && (b % 6)==1 )){
if((a>b)&&(a-b<b)){
return MCD(b,a-b);
}else if((a>b)&&(a-b>b)){
return MCD(a-b,b);
}else if((a<b)&&(b-a>a)){
return MCD(b-a,a);
}else if((a<b)&&(b-a<a)){
return MCD(a,b-a);
}
}
if(a>b){
if((a % 6)==1 && (b % 6)==1 ){
c=(a-1)/6;
d=(b-1)/6;
if(((c-d)>b)&&((c-d-b)<(a-c-d))){
return MCD(c-d,b);
}else if((c-d)<b){
return MCD(b,c-d);
}else if(((c-d)>b)&&((c-d-b)>(a-c-d))){
return MCD(a,c-d);
}
}else if((a % 6)==5 && (b % 6)==5 ){
c=(a-5)/6;
d=(b-5)/6;
if(((c-d)>b)&&((c-d-b)<(a-c-d))){
return MCD(c-d,b);
}else if((c-d)<b){
return MCD(b,c-d);
}else if(((c-d)>b)&&((c-d-b)>(a-c-d))){
return MCD(a,c-d);
}
}
}else if((a<b)&&((a % 6)==1 && (b % 6)==1 )){
c=(a-1)/6;
d=(b-1)/6;
if(((d-c)>a)&&((d-c-a)<(b-d-c))){
return MCD(d-c,a);
}else if((d-c)<a){
return MCD(a,d-c);
}else if(((d-c)>a)&&((a-c-b)>(b-d-c))){
return MCD(b,d-c);
}
}else if((a<b)&&((a % 6)==5 && (b % 6)==5) ){
c=(a-5)/6;
d=(b-5)/6;
if(((d-c)>a)&&((d-c-a)<(b-d-c))){
return MCD(d-c,a);
}else if((d-c)<a){
return MCD(a,d-c);
}else if(((d-c)>a)&&((a-c-b)>(b-d-c))){
return MCD(b,d-c);
}
}
}
Ho fatto un mix Euclide Lepore
HO AUMENTATO I CICLI E DIMINUITO I TEMPI DI CALCOLO
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int main()
{
int valMCD=1;
int a=0;
int b=0;
int rip=1;
int i=0;
int j=0;
int k=0;
int e=0;
printf("Inserisci il primo numero\n");
scanf("%d",&a);
printf("Inserisci il secondo numero\n");
scanf("%d",&b);
while(a % 2 == 0){ a=a/2; i++;}
while(a % 3 == 0){ a=a/3; j++;}
while(b % 2 == 0){ b=b/2; k++;}
while(b % 3 == 0) {b=b/3; e++;}
if ((i!=0 && k!=0)&&(i>=k)) {
rip=rip*pow(2,k);
}else if ((i!=0 && k!=0)&&(i<=k)){
rip=rip*pow(2,i);
}
if ((j!=0 && e!=0)&&(j>=e)) {
rip=rip*pow(3,e);
}else if ((j!=0 && e!=0)&&(j<=e)){
rip=rip*pow(3,j);
}
valMCD=(MCD(a,b))*rip;
printf("valMCD=%d",valMCD);
}
int MCD(a,b){
printf("a=%d\nb=%d\n",a,b);
int c=0;
int d=0;
while(a % 2 == 0){ a=a/2; }
while(a % 3 == 0){ a=a/3; }
while(b % 2 == 0){ b=b/2; }
while(b % 3 == 0) {b=b/3; }
if( (a % b)==0){
return b;
}else if ((b % a)==0){
return a;
}
if ((((a % 6)==1) && ((b % 6)==5) )|| ((a % 6)==5 && (b % 6)==1 )){
if(a>b){ return MCD(a,a-b);}
else {return MCD(b,b-a);}
}
if(a>b){
if((a % 6)==1 && (b % 6)==1 ){
c=(a-1)/6;
d=(b-1)/6;
return MCD(a,c-d);
}else{
c=(a-5)/6;
d=(b-5)/6;
return MCD(a,c-d);
}
}else if(a<b){
if((a % 6)==1 && (b % 6)==1 ){
c=(a-1)/6;
d=(b-1)/6;
return MCD(b,d-c);
}
}else{
c=(a-5)/6;
d=(b-5)/6;
return MCD(b,d-c);
}
}
Ti dico quello che dico sempre ai miei studenti. Un codice senza commenti e' illeggibile per chiunque non lo abbia scritto (e diventa illeggibile anche per chi lo ha scritto dopo due settimane). Inoltre se si vuole presentare del codice, si deve prima spiegare in dettaglio cosa fa e come lo fa.
Quando rispondi, ti pregherei di non farlo riproponendo il link proposto al primo post perche' anche io, credo come Martino, non ci vedo nulla se non il considerare prima dei fattori 2 e 3 e poi fare cose che non si capiscono con quel che rimane.
Quando rispondi, ti pregherei di non farlo riproponendo il link proposto al primo post perche' anche io, credo come Martino, non ci vedo nulla se non il considerare prima dei fattori 2 e 3 e poi fare cose che non si capiscono con quel che rimane.
Breve spiegazione del codice sottostante:
L'algoritmo per prima cosa vede se ci sono fattori comuni potenze di 2 e di 3.
Poi chiama la funzione MCD dove gli argomenti sono due numeri a e b derivanti dalla divisone per le potenze di 3 e di 2.
Se tali numeri non sono entrambi nella forma 6k+1 o entrambi nella forma 6k+5 allora usa euclide e richiama la funzione MCD con la differenza minore (cioè se a>b && b>a-b ->MCD(b,a-b) ecc.ecc.)
Se tali numeri sono entrambi nella forma 6k+1 o entrambi nella forma 6k+5 allora se a=6h+1 e b=6g+1 con a>b ->h-g è divisibile per Il massimo comun divisore analogamente si ha che se a=6h+5 e b=6g+5 con a>b ->h-g è divisibile per Il massimo comun divisore e richiama la funzione MCD con la differenza minore
gentilmente potreste dirmi qual'è la complessità computazionale
EDIT:
Ho capito il caso peggiore è quando a e b sono composti esclusivamente da potenze di 2 e di 3 quindi ho pensato di migliorarlo così:
L'algoritmo per prima cosa vede se ci sono fattori comuni potenze di 2 e di 3.
Poi chiama la funzione MCD dove gli argomenti sono due numeri a e b derivanti dalla divisone per le potenze di 3 e di 2.
Se tali numeri non sono entrambi nella forma 6k+1 o entrambi nella forma 6k+5 allora usa euclide e richiama la funzione MCD con la differenza minore (cioè se a>b && b>a-b ->MCD(b,a-b) ecc.ecc.)
Se tali numeri sono entrambi nella forma 6k+1 o entrambi nella forma 6k+5 allora se a=6h+1 e b=6g+1 con a>b ->h-g è divisibile per Il massimo comun divisore analogamente si ha che se a=6h+5 e b=6g+5 con a>b ->h-g è divisibile per Il massimo comun divisore e richiama la funzione MCD con la differenza minore
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int main()
{
int valMCD=1;
int a=0;
int b=0;
int rip=1;
int i=0;
int j=0;
int k=0;
int e=0;
printf("Inserisci il primo numero\n");
scanf("%d",&a);
printf("Inserisci il secondo numero\n");
scanf("%d",&b);
while(a % 2 == 0){ a=a/2; i++;}
while(a % 3 == 0){ a=a/3; j++;}
while(b % 2 == 0){ b=b/2; k++;}
while(b % 3 == 0) {b=b/3; e++;}
if ((i!=0 && k!=0)&&(i>=k)) {
rip=rip*pow(2,k);
}else if ((i!=0 && k!=0)&&(i<=k)){
rip=rip*pow(2,i);
}
if ((j!=0 && e!=0)&&(j>=e)) {
rip=rip*pow(3,e);
}else if ((j!=0 && e!=0)&&(j<=e)){
rip=rip*pow(3,j);
}
valMCD=(MCD(a,b))*rip;
printf("valMCD=%d",valMCD);
}
int MCD(a,b){
printf("a=%d\nb=%d\n",a,b);
int c=0;
int d=0;
while(a % 2 == 0){ a=a/2; }
while(a % 3 == 0){ a=a/3; }
while(b % 2 == 0){ b=b/2; }
while(b % 3 == 0) {b=b/3; }
if( (a % b)==0){
return b;
}else if ((b % a)==0){
return a;
}
if ((((a % 6)==1) && ((b % 6)==5) )|| ((a % 6)==5 && (b % 6)==1 )){
if((a>b)&&(a-b<b)){
return MCD(b,a-b);
}else if((a>b)&&(a-b>b)){
return MCD(a-b,b);
}else if((a<b)&&(b-a>a)){
return MCD(b-a,a);
}else if((a<b)&&(b-a<a)){
return MCD(a,b-a);
}
}
if(a>b){
if((a % 6)==1 && (b % 6)==1 ){
c=(a-1)/6;
d=(b-1)/6;
if(((c-d)>b)&&((c-d-b)<(a-c-d))){
return MCD(c-d,b);
}else if((c-d)<b){
return MCD(b,c-d);
}else if(((c-d)>b)&&((c-d-b)>(a-c-d))){
return MCD(a,c-d);
}
}else if((a % 6)==5 && (b % 6)==5 ){
c=(a-5)/6;
d=(b-5)/6;
if(((c-d)>b)&&((c-d-b)<(a-c-d))){
return MCD(c-d,b);
}else if((c-d)<b){
return MCD(b,c-d);
}else if(((c-d)>b)&&((c-d-b)>(a-c-d))){
return MCD(a,c-d);
}
}
}else if((a<b)&&((a % 6)==1 && (b % 6)==1 )){
c=(a-1)/6;
d=(b-1)/6;
if(((d-c)>a)&&((d-c-a)<(b-d-c))){
return MCD(d-c,a);
}else if((d-c)<a){
return MCD(a,d-c);
}else if(((d-c)>a)&&((a-c-b)>(b-d-c))){
return MCD(b,d-c);
}
}else if((a<b)&&((a % 6)==5 && (b % 6)==5) ){
c=(a-5)/6;
d=(b-5)/6;
if(((d-c)>a)&&((d-c-a)<(b-d-c))){
return MCD(d-c,a);
}else if((d-c)<a){
return MCD(a,d-c);
}else if(((d-c)>a)&&((a-c-b)>(b-d-c))){
return MCD(b,d-c);
}
}
}gentilmente potreste dirmi qual'è la complessità computazionale
EDIT:
Ho capito il caso peggiore è quando a e b sono composti esclusivamente da potenze di 2 e di 3 quindi ho pensato di migliorarlo così:
While(a%b!=0 && ((a%2==0 && b%2==0 ) ||(a%3==0 && b%3==0))) {
if(a % 2 == 0){ a=a/2; i++;}
if(a % 3 == 0){ a=a/3; j++;}
if(b % 2 == 0){ b=b/2; k++;}
if(b % 3 == 0) {b=b/3; e++;}
}
Prima cosa. Tu stai dicendo che se $a = 6 h + 1$ e $b = 6g+1$, allora se $d | a,b$ (con $d \ne 2,3$) si ha che $d | h-g$. E questo mi torna.
Quindi parti con $a$ e $b$, calcoli $g$ e $h$ e riparti con $b$ al posto di $a$ e $g-h$ al posto di $b$ (con leggere modifiche per mantenere la congruenza modulo $6$).
Ho due dubbi:
- Il primo e' sulla correttezza: come fai a garantire che il MCD di $a,b$ sia lo stesso di $b$ e $g-h$ (a meno di fattori $2,3$) e non magari un suo multiplo?
- Il secondo e' sulla complessita': sembrerebbe che ad ogni passo, genericamente, i dati vengono divisi per un fattore $6$ (forse qualcosa di meglio, facciamo $12$). Quindi la complessita' resta comunque esponenziale (fai $O(n/12)$ passi se $n$ e' l'ordine di grandezza dei tuoi dati iniziali). Come puoi sperare che questo sia meglio dell'algoritmo di Euclide, che invece e' polinomiale?
Quindi parti con $a$ e $b$, calcoli $g$ e $h$ e riparti con $b$ al posto di $a$ e $g-h$ al posto di $b$ (con leggere modifiche per mantenere la congruenza modulo $6$).
Ho due dubbi:
- Il primo e' sulla correttezza: come fai a garantire che il MCD di $a,b$ sia lo stesso di $b$ e $g-h$ (a meno di fattori $2,3$) e non magari un suo multiplo?
- Il secondo e' sulla complessita': sembrerebbe che ad ogni passo, genericamente, i dati vengono divisi per un fattore $6$ (forse qualcosa di meglio, facciamo $12$). Quindi la complessita' resta comunque esponenziale (fai $O(n/12)$ passi se $n$ e' l'ordine di grandezza dei tuoi dati iniziali). Come puoi sperare che questo sia meglio dell'algoritmo di Euclide, che invece e' polinomiale?
Ora dovrebbe essere più veloce di euclide
int MCD(a,b){//supponendo che siano stati divisi già per le potenze di 2 e di 3 e che inizialmente a >b
printf("a=%d\nb=%d\n",a,b);
while(a % 2 == 0){ a=a/2; }
while(a % 3 == 0){ a=a/3; }
while(b % 2 == 0){ b=b/2; }
while(b % 3 == 0) {b=b/3; }
if( (a % b)==0){
return b;
}
if ((((a % 6)==1) && ((b % 6)==1) )|| ((a % 6)==5 && (b % 6)==5 )){
if(b>(a-b)/6){
return MCD(b,b%((a-b)/6));
}else{
return MCD(a,a%((a-b)/6));
}
}
else{
return MCD(b,(a%b));
}
}
[xdom="vict85"]Sposto in informatica.[/xdom]
Comunque non mi sembra che sia corretto: i multipli comuni di 2 e 3 non vengono considerati nel MCD. Comunque le divisioni per 3 non sono operazioni comode per il computer.
Comunque non mi sembra che sia corretto: i multipli comuni di 2 e 3 non vengono considerati nel MCD. Comunque le divisioni per 3 non sono operazioni comode per il computer.
Ma la di la' di quello, io sto cercando di capire l'algoritmo (che come al solito nei post P_1_6 e' un'impresa).
Mi sta benissimo ridurre le potenze di $2$ e $3$ inizialmente (o di qualunque numero fissato di fattori piccoli (ad esempio tutti i primi piu' piccoli di $1000$)): non cambiera' di una virgola la complessita' asintotica dell'algoritmo.
Ma nonostante questo, la mia obiezione sulla correttezza sollevata nel post precedente resta senza risposta.
Infine, come ho detto prima, cosi' a occhio l'algoritmo proposto, anche se fosse corretto, non e' polinomiale (non parlo del codice...prima del codice cerchiamo di dare un filo di forma alla teoria).
Visto che la discussione e' stata spostata in informatica, sollevo una domanda di natura un pochino diversa: c'e' una ragione ovvia per cui il calcolo del MCD e' \(\mathbf{P}\)-completo? O risultati di questo genere?
Mi sta benissimo ridurre le potenze di $2$ e $3$ inizialmente (o di qualunque numero fissato di fattori piccoli (ad esempio tutti i primi piu' piccoli di $1000$)): non cambiera' di una virgola la complessita' asintotica dell'algoritmo.
Ma nonostante questo, la mia obiezione sulla correttezza sollevata nel post precedente resta senza risposta.
Infine, come ho detto prima, cosi' a occhio l'algoritmo proposto, anche se fosse corretto, non e' polinomiale (non parlo del codice...prima del codice cerchiamo di dare un filo di forma alla teoria).
Visto che la discussione e' stata spostata in informatica, sollevo una domanda di natura un pochino diversa: c'e' una ragione ovvia per cui il calcolo del MCD e' \(\mathbf{P}\)-completo? O risultati di questo genere?
"Pappappero":
Ma la di la' di quello, io sto cercando di capire l'algoritmo (che come al solito nei post P_1_6 e' un'impresa).
Mi sta benissimo ridurre le potenze di $2$ e $3$ inizialmente (o di qualunque numero fissato di fattori piccoli (ad esempio tutti i primi piu' piccoli di $1000$)): non cambiera' di una virgola la complessita' asintotica dell'algoritmo.
Ma nonostante questo, la mia obiezione sulla correttezza sollevata nel post precedente resta senza risposta.
Infine, come ho detto prima, cosi' a occhio l'algoritmo proposto, anche se fosse corretto, non e' polinomiale (non parlo del codice...prima del codice cerchiamo di dare un filo di forma alla teoria).
Visto che la discussione e' stata spostata in informatica, sollevo una domanda di natura un pochino diversa: c'e' una ragione ovvia per cui il calcolo del MCD e' \(\mathbf{P}\)-completo? O risultati di questo genere?
Mi associo alle questione sollevate da pappappero
Aspettiamo qualcuno più esperto di noi che ci aiuti
Questo algoritmo generalizza un algoritmo ben noto per calcolare il mcd:
il cosidetto "binary gcd algorithm". Si tratta di un algoritmo polinomiale.
Asintoticamente il binary gcd algorithm e l'algoritmo proposto qua hanno
la stessa complessita': quella del solito algoritmo euclideo.
Siccome di solito i computer fanno i calcoli in base $2$, la divisione per $2$
e' un'operazione molto veloce in pratica. Questo potrebbe essere un
vantaggio per il binary gcd algorithm.
L'algoritmo proposto qua ha lo stesso vantaggio
per i computer che fanno i calcoli in base $6$.
il cosidetto "binary gcd algorithm". Si tratta di un algoritmo polinomiale.
Asintoticamente il binary gcd algorithm e l'algoritmo proposto qua hanno
la stessa complessita': quella del solito algoritmo euclideo.
Siccome di solito i computer fanno i calcoli in base $2$, la divisione per $2$
e' un'operazione molto veloce in pratica. Questo potrebbe essere un
vantaggio per il binary gcd algorithm.
L'algoritmo proposto qua ha lo stesso vantaggio
per i computer che fanno i calcoli in base $6$.
grazie, mi hai insegnato un altro approccio
Ho trovato questo in rete
1. If |b| > |a|, return Binary-Gcd(b, a).
2. If b = 0, return a.
3. If a and b are both even then return 2 · Binary-Gcd(a/2, b/2).
4. If a is even and b is odd then return Binary-Gcd(a/2, b).
5. If a is odd and b is even then return Binary-Gcd(a, b/2).
6. Otherwise return Binary-Gcd((|a| − |b|)/2, b)
Supponendo che la divisione per 6 impiega il doppio del tempo della divisione per 2
Da che punto in poi non è un vantaggio?
Ho trovato questo in rete
1. If |b| > |a|, return Binary-Gcd(b, a).
2. If b = 0, return a.
3. If a and b are both even then return 2 · Binary-Gcd(a/2, b/2).
4. If a is even and b is odd then return Binary-Gcd(a/2, b).
5. If a is odd and b is even then return Binary-Gcd(a, b/2).
6. Otherwise return Binary-Gcd((|a| − |b|)/2, b)
"Stickelberger":
Questo potrebbe essere un
vantaggio per il binary gcd algorithm.
Supponendo che la divisione per 6 impiega il doppio del tempo della divisione per 2
Da che punto in poi non è un vantaggio?
"Pappappero":
Visto che la discussione e' stata spostata in informatica, sollevo una domanda di natura un pochino diversa: c'e' una ragione ovvia per cui il calcolo del MCD e' \(\mathbf{P}\)-completo? O risultati di questo genere?
A detta di wiki non si sa se il problema è o meno \(\mathbf{P}\)-completo, e lo stesso vale per cose simili. https://en.wikipedia.org/wiki/Greatest_common_divisor
Inoltre esistono già algoritmi più efficienti di Euclide, ma richiedono tutti una complessità di codice molto superiore. In questo senso sono poco utili per numeri che sono al di sotto di 32 o 64bit e per cui divisioni e sottrazioni sono piuttosto efficienti.
------------------------------------------
Io comunque sono dell'opinione che tra i principianti ci sia spesso un abuso dei commenti. Insomma generalmente o non ci sono o sono usati male. Entrambe le situazioni sono decisamente fastidiose e io personalmente trovo che troppi commenti inutili siano peggio di non scrivere alcun commento, perché richiedono al lettore di saltare righe e cose simili.
Il codice di P_1_6, al di là del fatto che non è un codice C valido, non è difficile da leggere; il difficile è comprendere se può essere reso corretto. Un paio di commenti sarebbero sufficienti. Detto questo anche se fosse reso corretto non avrebbe complessità asintotica migliore del normale algoritmo euclideo e certamente ha performance peggiori (a occhio avrebbe la stessa complessità ma con costanti più grandi).
"P_1_6":
Supponendo che la divisione per 6 impiega il doppio del tempo della divisione per 2
Da che punto in poi non è un vantaggio?
Il fatto che dividere per 6 non impiega il doppio del tempo ma 25-100 volte tanto (il tempo esatto dipende dall'hardware).
Ciao vict85
cosa devo cercare per capire la differenza tra dividere per 2 e per 6 in un sistema binario?
Perchè ho pensato che non può essere superiore al triplo in quanto basta dividere 3 volte per due
cosa devo cercare per capire la differenza tra dividere per 2 e per 6 in un sistema binario?
Perchè ho pensato che non può essere superiore al triplo in quanto basta dividere 3 volte per due
Dividere per $2$ in binario vuol dire spostare la virgola ...
"P_1_6":
Perchè ho pensato che non può essere superiore al triplo in quanto basta dividere 3 volte per due
Scusami ho commesso un errore
grazie axpgn
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo