Skip to main content

Euclid's Algorithm

The Greatest Common Divisor ( GCD ) of  two numbers is a number. The number ( GCD ) causes division of the two numbers. This number ( GCD ) is the greatest number that is possible. This divisor partially forms the two numbers. Adding  the divisor successively may result in formation of the two numbers.

One can note that when the divisor is the greatest, the division of the dividend is the sharpest. The division operation is very effective.

When the Greatest Common Divisor of two numbers is considered, we think of a number that can cause division of both the numbers. Here the two numbers are unequal. The Greatest Common Divisor causes divisions of the two numbers differently. This is clear from the two different quotient values. 

The GCD value is very interesting to note. It relates very well with the two numbers. The GCD of two even numbers is also an even number. The GCD of two odd numbers is an odd number. So, we can say that GCD is an abstraction of the two numbers in many ways. 

We can say that the GCD concept talks about mathematical connectivity. It stands to unite numbers in mathematical ways. It tells how maximal division of two numbers can be caused by a single number. 


_____________________________

Euclid's Algorithm:

This algorithm is used to calculate the

GCD of two numbers. 

Assumption: The first number is greater than the second. 


1 ) Input first number m

2 ) Input second number n

3) r = m % n

4 ) if r = 0

       Print n is GCD

       Goto Step ( 6 )

5 ) m = n

      n = r

      Goto Step ( 3 )

6 ) Stop

____________________________

Algorithm Tracing Activity l:

Pass I:-

1 ) m = 8

2 ) n = 4

3 ) r = m % n = 8 % 4 = 0

4 ) If r = 0 ( Yes )

       4 ( = n ) is the GCD

       Goto Step ( 6 )

6 ) Stop 


___________________________


___________________________

Algorithm Tracing Activity ll:


Pass I:

1 ) m = 18

2 ) n = 12

3 ) r = m % n = 18 % 12 = 6

4 ) r = 0 ( No )

5 ) m = n 

     Hence m = 12

     n = r

     Hence n = 6

     Goto Step ( 3 )

#########

For Pass II 

 ( Valid Intermediate Values ):

       m = 12

       n = 6

#########

_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _

Pass II:


( 3 ) r = m % n 

          =  12 % 6 ( From Pass I )

          = 0

( 4 ) if r = 0 ( Yes )

         Print 6 ( = n ) is GCD

         Goto Step ( 6 )

( 6 ) Stop

_____________________________

   

Labels:

Comments

Post a Comment

Popular posts from this blog

Interface Message Processor ( IMP )

Interface Message Processor ( IMP ) is a special purpose Computer. The Processor plays a vital role in Host-to-Host communication. IMP is placed between Host Computers.  IMP helps Hosts to exchange information. IMPs ( Interface Message Processors ) form a group. The group dedicates itself towards reliable transmission of Packets. _________________________ Note: An Interface Message Processor can be supposed to have a face. Firstly this supposed face of IMP is in the direction of the first Host, which sends the  message. Secondly, this face is turned towards the other Host.  Now, the IMP,  with its face turned around, communicates with this other Host.  Transformed message from IMP is communicated to this Host. __________________________ Message ( a piece of information ) sent from the Host ( source of information  ) is transformed into Packets. Transformation of the message into Packets is performed by an IMP. These Packets are forwarded to the receiver H...
Post a Comment
Read more

Understanding Distribution

Distributed presence means that more than one object is there. Also, these objects are situated at more than one location.  One object may establish communication with another object. The first object may deliver some message. The message can be received by another object. It can be said that object distribution is successful, as one object has succeeded in delivering a message. The second object has successfully received the message. Two objects are at a distance. Communication brings them closer. The successful communication has served to highlight that the idea of distribution is meaningful. Distribution helps exchange of information. Many different objects can form a group.  Two groups can occupy different locations.  It may happen that at a particular location there are several objects. But, all these objects talk among themselves.They talk among themselves and make things happen.  There is a resultant of this talk process. All the communicating objects  at...
Post a Comment
Read more

Message Switching

Message is a piece of information. Switching means movement.  In a Network there are a number of nodes. Nodes are vital junctions of a Network. Message Switching means transmission from one node ( one point ) of a Network to another node ( another point ). So, transmission is from point to point. Transmission from one point to another point is a single hop ( jump ). Message Switching means switch over of a Message. In one step of Message Switching,  Message switches over from one node to another.  The two nodes involved in a Switching operation are on the same Network. It cannot be that the beginning node ( source node) is on one Network and the second node ( sink node ) is on a different Network. In a point to point ( one junction to another junction ) transmission, a Message travels a part of its journey. Message moves from previous point to next point. The Network is Point-to-Point Network. A Switching activity means movement of a message. Indeed, the Message has mov...
Post a Comment
Read more