Euclid Algorithm (extended)
The Euclid Algorithm (expanded) is as follows...
Code:
//The algorithm(not written in any languaje, just the algorithm)--
ext_gcd(int m, int n){
if(n==0) return (m,1,0);
(d',m",n")=ext_gcd(n,m%n);
(d,m',n')=(d',n",m"-floor(m/n)*n");
return (d,m',n");
}
as simple as that :D
(in case you don't remember the Euclid algorithm...is as simple as follows:
Code:
int gcd(int m, int n){
if(n==0) return m;
else return gcd(n,m%n);
}
us used to find the greatest common divisor of two numbers,
but in the expanded version not only finds that... also finds the two factors.
for example:
if i want to calculate the gcd of 954 and 288
with this algorithm (by recursion)i should be able to find that:
gcd(18,0)=18=18*1+0*0
gcd(90,18)=18=90*0+18*1
gcd(288,90)=18=90*1+18*(-3) and finally...
gcd(954,288)=18=954(-3)+288(10)
So i want a program that shows me not only the result ... but also the factors and print them out like just now...
I wrote the following but have errors......
Code:
#include<stdio.h>
#include<math.h>
#include"malloc.h"
typedef struct euclid{
int m;
int a;
int b;
}Euclid;
int * ext_gcd(int m, int n){
Euclid *euclidp;
if(n==0) {
euclidp->m=m;
euclidp->a=1;
euclidp->b=0;
printf("ext_gcd(%d,%d)=%d=%d*%d+%d*%d\n",m,n,euclidp->m,m,euclidp->a,n,euclidp->b);
return euclidp;
}
euclidp2=(struct euclid *)malloc(sizeof(struct euclid));
euclidp2=ext_gcd(n, m%n);
euclidp2->m=euclid->m;
euclidp2->a=euclid->b;
euclidp2->b=(euclid->a)-floor(m/n)*(euclid->b);
printf("ext_gcd(%d,%d)=%d=%d*%d+%d*%d\n",m,euclidp2->m,m,euclipd2->a,n,euclipd2->b);
return euclid2;
}
int main(){
printf("Euclid Method (Extended)\n");
ext_gcd(954,288);
return 0;
}
and the errors...
Code:
i60-41-152-52:~/Desktop/tuesday4_2mac nacho$ gcc 1206_2.c
1206_2.c: In function 'ext_gcd':
1206_2.c:16: warning: return from incompatible pointer type
1206_2.c:18: error: 'euclidp2' undeclared (first use in this function)
1206_2.c:18: error: (Each undeclared identifier is reported only once
1206_2.c:18: error: for each function it appears in.)
1206_2.c:18: warning: incompatible implicit declaration of built-in function 'malloc'
1206_2.c:20: error: 'euclid' undeclared (first use in this function)
1206_2.c:23: error: 'euclipd2' undeclared (first use in this function)
1206_2.c:24: error: 'euclid2' undeclared (first use in this function)
i60-41-152-52:~/Desktop/tuesday4_2mac nacho$
please.. help me... :lol:
sorry..., i corrected my code... a little bit
Code:
#include<stdio.h>
#include<math.h>
#include"malloc.h" /*please don't care about my malloc..., its ok this way. in windows.. this line should be #include <malloc.h>*/
typedef struct euclid{
int m;
int a;
int b;
}Euclid;
int * ext_gcd(int m, int n){
Euclid *euclidp;
if(n==0) {
euclidp->m=m;
euclidp->a=1;
euclidp->b=0;
printf("ext_gcd(%d,%d)=%d=%d*%d+%d*%d\n",m,n,euclidp->m,m,euclidp->a,n,euclidp->b);
}
return ext_gcd(n,m%n);
euclidp2=(Euclid *)malloc(sizeof(Euclid));
euclidp2=ext_gcd(n, m%n);
euclidp2->m=euclidp->m;
euclidp2->a=euclidp->b;
euclidp2->b=(euclidp->a)-floor(m/n)*(euclidp->b);
printf("ext_gcd(%d,%d)=%d=%d*%d+%d*%d\n",m,euclidp2->m,m,euclipd2->a,n,euclipd2->b);
return euclidp2;
}
int main(){
printf("Euclid Method (Extended)\n");
ext_gcd(954,288);
return 0;
}
but i still have errors..
Code:
i60-41-152-52:~/Desktop/tuesday4_2mac nacho$ gcc 1206_2.c -lm
1206_2.c: In function 'ext_gcd':
1206_2.c:18: error: 'euclidp2' undeclared (first use in this function)
1206_2.c:18: error: (Each undeclared identifier is reported only once
1206_2.c:18: error: for each function it appears in.)
1206_2.c:18: warning: incompatible implicit declaration of built-in function 'malloc'
1206_2.c:23: error: 'euclipd2' undeclared (first use in this function)
i60-41-152-52:~/Desktop/tuesday4_2mac nacho$
sorry..,I CORRECED SOME MISTAKES..
Code:
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
typedef struct euclid{
int m;
int a;
int b;
}Euclid;
Euclid * ext_gcd(int m, int n){
Euclid *euclidp;
if(n==0) {
euclidp->m=m;
euclidp->a=1;
euclidp->b=0;
printf("ext_gcd(%d,%d)=%d=%d*%d+%d*%d\n",m,n,euclidp->m,m,euclidp->a,n,euclidp->b);
return euclidp;
}
euclidp2=(Euclid *)malloc(sizeof(Euclid));
euclidp2=ext_gcd(n, m%n);
euclidp2->m=euclidp->m;
euclidp2->a=euclidp->b;
euclidp2->b=(euclidp->a)-floor(m/n)*(euclidp->b);
printf("ext_gcd(%d,%d)=%d=%d*%d+%d*%d\n",m,euclidp2->m,m,euclipd2->a,n,euclipd2->b);
return euclidp2;
}
int main(){
printf("Euclid Method (Extended)\n");
ext_gcd(954,288);
return 0;
}
and my errors
Code:
i60-41-152-52:~/Desktop/tuesday4_2mac nacho$ gcc 1206_2.c -lm1206_2.c: In function 'ext_gcd':
1206_2.c:18: error: 'euclidp2' undeclared (first use in this function)
1206_2.c:18: error: (Each undeclared identifier is reported only once
1206_2.c:18: error: for each function it appears in.)
1206_2.c:23: error: 'euclipd2' undeclared (first use in this function)
i60-41-152-52:~/Desktop/tuesday4_2mac nacho$
what should I do?? why cant i declare euclipd2 with malloc??
the part that:"Try to figure out what..."
what should I write???
I need two Euclid variables.. so if i declare another one inside the function it won't be same as my code before?