Re: Extended Euclidean algorithm for java
On May 19, 2:47 pm, thread <yaniv...@gmail.com> wrote:
does anyone know the code for the Extended Euclidean algorithm
while
gcd(x,y)=s*x+t*y
the basic idea is to follow the steps of the normal algorithm and to
take to account the follow equation:
a=s*x+t*y
b=u*x+v*y
i [sic] dont know how to translate it to a coding
any ideas?
Is this homework? If so, have you tried your normal academic
resources for guidance?
Have you tried Wikipedia?
<http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm>
Basic approach to making an algorithm into a class:
Name the class:
package learning; // I assume you've learned about packages by now
public class GCD
{
}
Give it a method to do the calculation. This requires choosing the
argument and return types. If you make the class an interface at
first, you don't have to specify the actual method body.
package learning;
public interface GCD
{
public int calculate( int x, int y );
}
Now create an implementing class.
package learning;
public class ExtendedEuclideanGCD implements GCD
{
/** Calculate the Greatest Common Divisor (GCD) of two integer
terms.
* @param a int first term.
* @param b int second term.
* @return int GCD of the terms.
*/
public int calculate( int a, int b )
{
return 0; // temporary - prevent compiler error
}
}
Now you start creating the temporary variable of the algorithm as
method variables and plugging them into the equations.
package learning;
public class EuclideanGCD implements GCD
{
public int calculate( int a, int b )
{
int
x = 0, lastX = 1,
y = 1, lastY = 0;
while( b != 0 )
{
int quotient = a / b;
// etc.
}
return a;
}
}
There are some peculiar wrinkles I left out for now.
--
Lew