Thread: Euclid Algorithm (extended)

  1. #1
    Registered User
    Join Date
    Nov 2006
    Location
    japan
    Posts
    126

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

  2. #2
    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

  3. #3
    Registered User
    Join Date
    Nov 2006
    Location
    japan
    Posts
    126

    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$

  4. #4
    Registered User
    Join Date
    Nov 2006
    Location
    japan
    Posts
    126

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

  5. #5
    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

  6. #6
    Registered User
    Join Date
    Nov 2006
    Location
    japan
    Posts
    126
    so what should i do?

  7. #7
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    Euclid *euclidp;
    declares variable euclidp

    you should declare all variables used in the code
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

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

  9. #9
    Registered User
    Join Date
    Nov 2006
    Location
    japan
    Posts
    126

    Question ... look what happens..

    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?

  10. #10
    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.

  11. #11
    Registered User
    Join Date
    Nov 2006
    Location
    japan
    Posts
    126
    ************************************************** ******
    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.

  12. #12
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    [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;
    }
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

  13. #13
    Registered User
    Join Date
    Nov 2006
    Location
    japan
    Posts
    126

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

  14. #14
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    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
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 4
    Last Post: 12-10-2006, 07:08 PM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  4. Euclid Algorithm
    By Unregistered in forum C Programming
    Replies: 2
    Last Post: 07-01-2002, 10:27 PM