Euclid Algorithm (extended)

nacho4d · 12-06-2006, 08:11 AM

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:

Happy_Reaper · 12-06-2006, 08:34 AM

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.

nacho4d · 12-06-2006, 08:46 AM

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$

nacho4d · 12-06-2006, 09:00 AM

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

Happy_Reaper · 12-06-2006, 09:04 AM

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

nacho4d · 12-06-2006, 09:24 AM

so what should i do?

vart · 12-06-2006, 09:34 AM

Quote:

Euclid *euclidp;

declares variable euclidp

you should declare all variables used in the code

coder8137 · 12-06-2006, 09:57 AM

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).

nacho4d · 12-06-2006, 11:51 PM

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?

sl4nted · 12-07-2006, 12:08 AM

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

nacho4d · 12-07-2006, 01:30 AM

************************************************** ******
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.

vart · 12-07-2006, 01:45 AM

[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;
}

nacho4d · 12-07-2006, 02:45 AM

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?

vart · 12-07-2006, 02:56 AM

Quote:

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

12-06-2006, 08:34 AM	#2
Happy_Reaper Fear the Reaper... Join Date: Aug 2005 Location: Toronto, Ontario, Canada Posts: 625	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. __________________ Teacher: "You connect with Internet Explorer, but what is your browser? You know, Yahoo, Webcrawler...?" It's great to see the educational system moving in the right direction
Happy_Reaper is offline

12-06-2006, 09:04 AM	#5
Happy_Reaper Fear the Reaper... Join Date: Aug 2005 Location: Toronto, Ontario, Canada Posts: 625	Namely because malloc only allocates memory, it does not specify the type of euclidp2. __________________ Teacher: "You connect with Internet Explorer, but what is your browser? You know, Yahoo, Webcrawler...?" It's great to see the educational system moving in the right direction
Happy_Reaper is offline

12-06-2006, 09:24 AM	#6
nacho4d Registered User Join Date: Nov 2006 Location: japan Posts: 115	so what should i do?
nacho4d is offline

12-06-2006, 09:57 AM	#8
coder8137 Registered User Join Date: Nov 2006 Posts: 65	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).
coder8137 is offline

12-07-2006, 12:08 AM	#10
sl4nted Registered User Join Date: Nov 2006 Posts: 176	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 Last edited by sl4nted; 12-07-2006 at 12:10 AM.
sl4nted is offline

12-07-2006, 01:30 AM	#11
nacho4d Registered User Join Date: Nov 2006 Location: japan Posts: 115	************************************************ ** 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.
nacho4d is offline

12-07-2006, 01:45 AM	#12
vart CSharpener Join Date: Oct 2006 Posts: 5,328	[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; } __________________ If I have eight hours for cutting wood, I spend six sharpening my axe.
vart is offline

12-07-2006, 02:45 AM	#13
nacho4d Registered User Join Date: Nov 2006 Location: japan Posts: 115	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?
nacho4d is offline

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Euclid Algorithm (extended)Part2 Doubt about pointers - INITIALIZATION	nacho4d	C Programming	4	12-10-2006 07:08 PM
Binary Search Trees Part III	Prelude	A Brief History of Cprogramming.com	16	10-02-2004 03:00 PM
Request for comments	Prelude	A Brief History of Cprogramming.com	15	01-02-2004 10:33 AM
Euclid Algorithm	Unregistered	C Programming	2	07-01-2002 10:27 PM