Good day,

Could you kindly help me with the question below.

Research GCD algorithms, and analyze the Euclidean algorithm and Steiner’s algorithm.

How do they work?

What is their relative complexity?

Do you think one is “better” than the other? What factors influence your opinion?

Implement a GCD algorithm. Show your test data and results. When complete, email with subject: GCD, and have a text file with the source code, a text file with the test data, and a text file with the results of running the test data.

Write a program to create prime numbers, using iteration, and then again using recursion. Show the first 100 primes in your results file for each algorithm.

What are the advantages and disadvantages of using recursion, for example, in the prime number generator?

Expected results:

4 program (labs) : 2 GCD, 2 prime number. One each with recursion, and without recursion

1 writeup on Euclidean and Steiner’s Algorithm (1-2 pages)

1 writeup on advantages and disadvantages of recursion for problems such as these (1-2 pages)

In general for labs, submit:

-program .java source file

-test data

-test results (text file)

-any notes

*subject for the email should be the lab being submitted, such as: “GCD – recursion”

For writeups, please use a doc or docx file, and submit as an attachment. Kindly add a date, as it will help me keep track of your work. Eg: 170520GCDalgorithm.doc

## Expert Answer

**Euclid algorithm:**

In mathematics, the Euclidean algorithm[a], or Euclid’s algorithm, is an efficient method for computing the greatest common divisor (GCD) of two numbers, the largest number that divides both of them without leaving a remainder. It is named after the ancient Greek mathematician Euclid, who first described it in Euclid’s Elements (c. 300 BC). It is an example of an algorithm, a step-by-step procedure for performing a calculation according to well-defined rules, and is one of the oldest algorithms in common use. It can be used to reduce fractions to their simplest form, and is a part of many other number-theoretic and cryptographic calculations.

The Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number. For example, 21 is the GCD of 252 and 105 (as 252 = 21 × 12 and 105 = 21 × 5), and the same number 21 is also the GCD of 105 and 252 − 105 = 147. Since this replacement reduces the larger of the two numbers, repeating this process gives successively smaller pairs of numbers until the two numbers become equal. When that occurs, they are the GCD of the original two numbers. By reversing the steps, the GCD can be expressed as a sum of the two original numbers each multiplied by a positive or negative integer, e.g., 21 = 5 × 105 + (−2) × 252. The fact that the GCD can always be expressed in this way is known as Bézout’s identity.

The version of the Euclidean algorithm described above (and by Euclid) can take many subtraction steps to find the GCD when one of the given numbers is much bigger than the other. A more efficient version of the algorithm shortcuts these steps, instead replacing the larger of the two numbers by its remainder when divided by the smaller of the two (with this version, the algorithm stops when reaching a zero remainder). With this improvement, the algorithm never requires more steps than five times the number of digits (base 10) of the smaller integer. This was proven by Gabriel Lamé in 1844, and marks the beginning of computational complexity theory. Additional methods for improving the algorithm’s efficiency were developed in the 20th century

*package sample;*

*public class Euclid_Recursion {*

* // recursive implementation
public static int gcd(int p, int q) {
if (q == 0)
return p;
else
return gcd(q, p % q);
}*

* public static void main(String[] args) {
int p = 4;
int q = 8;
int d = gcd(p, q);*

* System.out.println(“gcd(” + p + “, ” + q + “) = ” + d);*

* }
}*

*package sample;*

*public class Euclid_Iteration {
// non-recursive implementation
public static int gcd2(int p, int q) {
while (q != 0) {
int temp = q;
q = p % q;
p = temp;
}
return p;
}*

* public static void main(String[] args) {
int p = 4;
int q = 8;*

* int d2 = gcd2(p, q);*

* System.out.println(“gcd(” + p + “, ” + q + “) = ” + d2);
}
}*

**Steiner’s algorithm:**

The binary GCD algorithm, also known as Stein’s algorithm, is an algorithm that computes the greatest common divisor of two nonnegative integers. Stein’s algorithm uses simpler arithmetic operations than the conventional Euclidean algorithm; it replaces division with arithmetic shifts, comparisons, and subtraction. Although the algorithm was first published by the Israeli physicist and programmer Josef Stein in 1967

algorithm reduces the problem of finding the GCD by repeatedly applying these identities:

- gcd(0, v) = v, because everything divides zero, and v is the largest number that divides v. Similarly, gcd(u, 0) = u. gcd(0, 0) is not typically defined, but it is convenient to set gcd(0, 0) = 0.
- If u and v are both even, then gcd(u, v) = 2·gcd(u/2, v/2), because 2 is a common divisor.
- If u is even and v is odd, then gcd(u, v) = gcd(u/2, v), because 2 is not a common divisor. Similarly, if u is odd and v is even, then gcd(u, v) = gcd(u, v/2).
- If u and v are both odd, and u ≥ v, then gcd(u, v) = gcd((u − v)/2, v). If both are odd and u < v, then gcd(u, v) = gcd((v − u)/2, u). These are combinations of one step of the simple Euclidean algorithm, which uses subtraction at each step, and an application of step 3 above. The division by 2 results in an integer because the difference of two odd numbers is even.[3]
- Repeat steps 2–4 until u = v, or (one more step) until u = 0. In either case, the GCD is 2kv, where k is the number of common factors of 2 found in step 2.

The algorithm requires O(n2)[4] worst-case time, where n is the number of bits in the larger of the two numbers. Although each step reduces at least one of the operands by at least a factor of 2, the subtract and shift operations take linear time for very large integers (although they’re still quite fast in practice, requiring about one operation per word of the representation).

*package sample;*

*public class Steiner_Recursion {
public static int gcd( int u, int v)
{
// simple cases (termination)
if (u == v)
return u;*

* if (u == 0)
return v;*

* if (v == 0)
return u;*

* // look for factors of 2
if (u%2==0) // u is even
{
if (v%2!=0) // v is odd
return gcd(u >> 1, v);
else // both u and v are even
return gcd(u >> 1, v >> 1) << 1;
}*

* if (v%2==0) // u is odd, v is even
return gcd(u, v >> 1);*

* // reduce larger argument
if (u > v)
return gcd((u – v) >> 1, v);*

* return gcd((v – u) >> 1, u);
}*

*public static void main(String[] args) {
System.out.println(gcd(4,8));
}*

*}*

*package sample;*

*public class Steiner_Iteration {
public static int gcd( int u, int v)
{
int shift;*

* /* GCD(0,v) == v; GCD(u,0) == u, GCD(0,0) == 0 */
if (u == 0) return v;
if (v == 0) return u;*

/* Let shift := lg K, where K is the greatest power of 2

dividing both u and v. */

for (shift = 0; ((u | v) & 1) == 0; ++shift) {

u >>= 1;

v >>= 1;

}

while ((u & 1) == 0)

u >>= 1;

*/* From here on, u is always odd. */
do {
/* remove all factors of 2 in v — they are not common */
/* note: v is not zero, so while will terminate */
while ((v & 1) == 0) /* Loop X */
v >>= 1;*

* /* Now u and v are both odd. Swap if necessary so u <= v,
then set v = v – u (which is even). For bignums, the
swapping is just pointer movement, and the subtraction
can be done in-place. */
if (u > v) {
int t = v; v = u; u = t;} // Swap u and v.
v = v – u; // Here v >= u.
} while (v != 0);*

* /* restore common factors of 2 */
return u << shift;
}*

*public static void main(String[] args) {
System.out.println(gcd(4,8));
}*

*}*

**Why not to use recursion**

- It is usually slower due to the overhead of maintaining the stack.
- It usually uses more memory for the stack.

**Why to use recursion**

- Recursion adds clarity and (sometimes) reduces the time needed to write and debug code (but doesn’t necessarily reduce space requirements or speed of execution).
- Reduces time complexity.
- Performs better in solving problems based on tree structures.