[Webinar] Streamline your web hosting managementRegister Today

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 1393
  • Last Modified:

Show Euclid's algorithm by using Basic or Pascal

Anyone have and idea please lend me a hand---->>
Explain and show using Basic or Pascal notation how Euclis's algorithm could be presented using a programming language. The algorithm must be shown, and explain by performing a program walkthrough for the algorithm.
thank you!!
0
ckchew666
Asked:
ckchew666
  • 8
  • 2
  • 2
  • +2
1 Solution
 
ozoCommented:
gcd(m,n):
         if n = 0
           answer is m
         else
           find gcd(n, m mod n)
0
 
_lychee_Commented:
ozo's correct, just make sure n<m
here's an implementation in basic:

if (m<n) then t=m:m=n:n=t
while n<>0
   t=n:n=m mod n:m=t
wend
'm contains gcd

?walkthrough?:
if u understand euclid's algo it shouldn't be a prob...

(4, 3) -> (3, 1) -> (1, 0) so 1...
0
 
_lychee_Commented:
haha... anyway i'm amused that i have seen abt 5 gcd qns all over since wed i think...
0
Free Tool: IP Lookup

Get more info about an IP address or domain name, such as organization, abuse contacts and geolocation.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

 
BigRatCommented:
Suppose the two numbers are a1 and a2 and that a2<=a1. Then
      a1 = q1*a2 + a3
(q1 may be just 1!)
   If a3 is zero the a2 divides a1 and is theefore the gcd.

   If a3 is non-zero then we would like to find a divisor of a3 and a2, say a4, such that a3=k1*a4 and a2=q2*a4 so that
     a1 = q1*(q2*a4) + (k1*a4)
So the process of finding a divisor for a2 and a3 is the same process as finding the divisor for a1 and a2. Hence the recurrence relationship :-

    gcd(a1,a2)=if a1 mod a2 =0 then a2 else gcd(a2,a1 mod a2) fi;

If you eliminate the mod function (occurs twice) by adding in another call level you get :-
   gcd(a1,a2)=if a2=0 then a1 else a1 mod a2 fi;
0
 
shlomoyCommented:
In Euclid's 7th book in the Elements series (written about 300BC), he gives an algorithm to calculate the
highest common factor (largest common divisor) of two numbers x and y where (x < y). This can be stated as:

  1.Divide y by x with remainder r.
  2.Replace y by x, and x with r.
  3.Repeat step 1 until r is zero.

When this algorithm terminates, y is the highest common factor.

As an example, consider trying to find the highest common factor of 34,017 and 16,966. Euclid's algorithm
works as follows:

    34,017/16,966 produces a remainder 85
    16,966/85 produces a remainder 51
    85/51 produces a remainder 34
    51/34 produces a remainder 17
    34/17 produces a remainder 0

and the highest common factor of 34,017 and 16,966 is 17.
0
 
shlomoyCommented:
The Euclidean algorithm is implemented by the following short JavaScript program:

// Assume that a>b
function gcd(a,b)
{
   // Loop until a or b is zero
   while (true)
   {
      a = a % b;
      if(a == 0) {return b;};
      b = b % a;
      if(b == 0) {return a;};
   };
   return b;
}

If you think carefully about the Euclidean algorithm you will see that at each step both numbers are formed by
adding some multiples of the original numbers. Thus there are some numbers, a and b, such that
gcd(n,m)=a*n+b*m. The Extended Euclidean algorithm can recover not only gcd(n,m), but also these numbers
a and b.
0
 
BatalfCommented:
Hi

Could this procedure help you(PASCAL/DELPHI)?

If you are familiar with Delphi, I here have a form, with 3 editcompnents, and one button. The formula is gcd(a,b).
Here : a= edit1.text, b=edit2.text and edit3.text is the result(gcd(a,b)) after pressing the button.

The procedure below is for the button:

Procedure findGCD;
var
   a,b,c,d,e,f : longint;
   gcd : string;
   numbers : array[1..20] of word;

begin
     a:=strtoint(edit1.text);
     b:=strtoint(edit2.text);
     {the clue is now to find gcd(a,b)}

     f:=0;
         repeat
         c:=trunc(a/b);
         d:=a-(c*b);
         inc(f);
         numbers[f]:=d;
         a:=c;
     until a=0;
     for a:=f downto 1 do
     edit3.text:=edit3.text+inttostr  (numbers[a]);
{ex : edit3.text gives 134100 if a=12564
     and b=6(12564 in base 6 is 134100)}

end;

Regards Batalf
0
 
BatalfCommented:
Or maybe this is more Correct(if I understood the algorithm wrong) :

The setup for the form is like I wrote above.

procedure TForm1.Button1Click(Sender: TObject);
var
   a,b,c,d,e : longint;
   gcb : longint;
begin
     a:=strtoint(edit1.text);
     b:=strtoint(edit2.text);
     repeat
           c:=trunc(a/b);
           d:=a-(c*b);
           if b<>0 then gcb:=b;
           a:=gcb;
           b:=d;
     until b=0;

     edit3.text:=inttostr(gcb);
end;

I used this website when I worked out this function :

http://www.unc.edu/~rowlett/Math81/spreadsheets/Euclid.html

I have tried it in Delphi my self, and its working.(ex : gcb(37170,12564) give me the value 18 as result)

Regards
Batalf
0
 
BatalfCommented:
Tried my solution ?
0
 
BatalfCommented:
Hi ckchew666

Have you tried the answer I proposed above?

Regards
Batalf
0
 
BatalfCommented:
Hi ckchew666

If you don't like my answer in Delphi,
maybe this one would help more(pure Pascal):

Program Euclid   ;
USES Crt;
var
   a,b,c,d,e : longint;
   gcb : longint;
   value1, value2 : string[10];  

begin

     readln(value1);
     readln(value2);
     repeat
           c:=trunc(a/b);
           d:=a-(c*b);
           if b<>0 then gcb:=b;
           a:=gcb;
           b:=d;
     until b=0;
     writeln('GCB = ',gcb);
end.







0
 
BatalfCommented:
Sorry, errors in my code above
This one is correct :

Program Euclid   ;
USES Crt;
var
   a,b,c,d,e : longint;
   gcb : longint;

begin

     readln(a);
     readln(b);

     repeat
           c:=trunc(a/b);
           d:=a-(c*b);
           if b<>0 then gcb:=b;
           a:=gcb;
           b:=d;
     until b=0;
     writeln('GCB = ',gcb);
     readkey;
end.

Best regards
Batalf
0
 
BatalfCommented:
??????????????????
0
 
BatalfCommented:
??
0

Featured Post

Keep up with what's happening at Experts Exchange!

Sign up to receive Decoded, a new monthly digest with product updates, feature release info, continuing education opportunities, and more.

  • 8
  • 2
  • 2
  • +2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now