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

(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:

Ok, so the problems, in order :

1) ext_gcd returns an int*, and you're returning Euclid*. This will make your compiler unhappy.
2) You don't declare euclidp2,euclid, or euclid2. You may know what these things is, but your compiler doesn't. Make sure to mention that to him if you want him to do his job.
3) Your compiler can't find the malloc function, namely because it is included in stdlib.h and you include that nowhere.

Further, notice that many of my corrections are almost exactly what your compiler told you to do in the first place. That's good. Ususally you'd want your compiler to tell you what and where your errors are.

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$

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??

Namely because malloc only allocates memory, it does not specify the type of euclidp2.

so what should i do?

Euclid *euclidp;

declares variable euclidp

you should declare all variables used in the code

Code:

Euclid *euclidp;
	if(n==0) {
		euclidp->m=m;

Unrelated to the things mentioned above. You need to initialize the pointer before you use it (for example with malloc).

This is my code ... I fixed it .. so now it has no errors (even though i still dont have the factors i wanted,... but thats a nother think i will think later.)

Code:

#include<stdio.h>
#include<math.h>
#include<malloc.h>
typedef struct euclid{
  int m;
  int a;
  int b;
}Euclid;
Euclid  ext_gcd(int m, int n){
  Euclid euclidp, euclidp2;
  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=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,euclidp2.a,n,euclidp2.b);
  return euclidp2;
}
int main(){
  printf("Euclid Algorithm (Extended)\n");
  ext_gcd(954,288);
  return 0;
}

I realized that it is not necesary pointers... so i did it with out them.

and i got :

Code:

[l05013@oli001 ~/tuesday4_2]$ ./a.out
Euclid Algorithm (Extended)
ext_gcd(18,0)=18=18*1+0*0
ext_gcd(90,1074095270)=90=1074037868*18+-2147483648*1073827124
ext_gcd(288,0)=288=0*90+0*134513212
ext_gcd(954,-1073743448)=954=1075289408*288+-2147483648*0
[l05013@oli001 ~/tuesday4_2]$ emacs 1206_2_03.c

wich is at least something... (no compiling errors)

but What i want to ask you.
is what if i want to do it with pointers?

Code:

#include<stdio.h>
#include<math.h>
#include<malloc.h>
typedef struct euclid{
  int m;
  int a;
  int b;
}Euclid;
Euclid  * ext_gcd(int m, int n){
  Euclid *euclidp, *euclidp2;
  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=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,euclidp2->a,n,euclidp2->b);
  return euclidp2;
}
int main(){
  printf("Euclid Algorithm (Extended)\n");
  ext_gcd(954,288);
  return 0;
}

it would be something like this but and i can compile it in my Mac(Unix terminal on Mac), but when executing it.. is says Segmentation Fault!
i run the debugger and as far as I understood... is said to me that is trying to access a part of the memory which i dont't have permission.
(Further more.. my kernel has that proteccion.)

in windows..(Unix terminal on Windows) well it doesn not compile.
it says...
[l05013@oli001 ~/tuesday4_2]$ gcc 1206_2.c -lm
/usr/lib/gcc-lib/i386-vine-linux/3.3.2/../../../crt1.o(.text+0x18): In function `_start':
: undefined reference to `main'
collect2: ld ended in status 1
[l05013@oli001 ~/tuesday4_2]$

what does it mean?? and how can i get this program well compiled?

it means your trying to access memory your not allowed to.
you have to use malloc to assign memory to euclidp, euclidp2 before you try to assign values to any of there members

this compiled for you?, where is floor defined? is it some windows thing

************************************************** ******
floor is a predefined function in math.h
to compile it in unix:

Code:

$gcc filename.c -lm

and run it with:

Code:

$./a.out

OR

Code:

$gcc filename.c -lm -o executablefilename

to build an executable file named executablefilename
and run this new one with

Code:

$./executablefilename

************************************************** ******
Well.
but ...
I already know that i am not allowed to that memory... but. then What should I do??? I simply don't know what to do me the segmentation fault... or segmentation error or Bus Errors comes up.

[quote=nacho4d I simply don't know what to do me the segmentation fault... or segmentation error or Bus Errors comes up.[/quote]
You are using pointer that is not initialized, so you are writing to some random address.

You can try to create the variable in the main function and provide it to your ext_gcd function to store the data.
Like this:

Code:

typedef struct euclid{
 int m;
 int a;
 int b;
}Euclid;
void ext_gcd(int m, int n, Euclid  * pEuclid)
{
 if(n==0) 
 {
  pEuclid->m=m;
  pEuclid->a=1;
  pEuclid->b=0;
  printf("ext_gcd(%d,%d)=%d=%d*%d+%d*%d\n",m,n,pEuclid->m,m,pEuclid->a,n,pEuclid->b);
 }
 else
 {
  //try to figure out what will be here
 }
 
 return;
}
int main()
{
 Euclid euclidObj; //this variable will store the result
 
 printf("Euclid Algorithm (Extended)\n");
 ext_gcd(954,288, &euclidObj);
 //now euclidObj contains the data calculated by the ext_gcd
 return 0;
}

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?

i declare another one inside the function

if you'll declare it as a pointer - yes you will have same problem
but if you'll declare it as an object of type Euclid - it will be possible to store there temporary data.
Bu the actual data to be returned to the calling function should be stored in the variable point by the pEuclid pointer