# Effective formal algorithm for computing GCD

by Thanh Hosy   Last Updated October 21, 2018 05:20 AM

Hello everybody I am currently so stuck at solving this problem in the first Volume of The Art of Computer Programming:

[M25] Give an "effective" formal algorithm for computing the greatest common divisor of positive integers $$m$$ and $$n$$, by specifying $$\theta_j$$, $$\phi_j$$, $$a_j$$, $$b_j$$ as in Eqs. (3). Let the input be represented by the string $$a^mb^n$$, that is, $$m$$ $$a$$'s followed by $$n$$ $$b$$'s. Try to make your solution as simple as possible. [$$Hint$$: Use Algorithm E, but instead of division in step E1, set $$r \leftarrow |m-n|$$, $$n \leftarrow min(m,n)$$.]

Now this is the part related to Eqs. (3):
Let $$A$$ be a finite set of letters, and let $$A^*$$ be the set of all strings on $$A$$ (the set of all ordered sequences $$x_1x_2...x_n$$, where $$n \ge 0$$ and $$x_j$$ is in $$A$$ for $$1 \le j \le n$$). The idea is to encode the states of the computation so that they are represented by strings of $$A^*$$. Now let $$N$$ be a nonnegative integer and let $$Q$$ be the set of all $$(\sigma,j)$$, where $$\sigma$$ is in $$A^*$$ and $$j$$ is an integer, $$0 \le j \le N$$; let $$I$$ be the subset of $$Q$$ with $$j=0$$ and let $$\Omega$$ be the subset with $$j=N$$. If $$\theta$$ and $$\sigma$$ are strings in $$A^*$$, we say that $$\theta$$ occurs in $$\sigma$$ if $$\sigma$$ has the form $$\alpha\theta\omega$$ for strings $$\alpha$$ and $$\omega$$. To complete our definition, let $$f$$ be a function of the following type, defined by the strings $$\theta_j$$, $$\phi_j$$ and the integers $$a_j$$, $$b_j$$ for $$0 \le j < N$$:
$$f(\sigma,j)=(\sigma, a_j)$$ if $$\theta_j$$ does not occur in $$\sigma$$;
$$f(\sigma,j)=(\alpha\phi_j\omega,b_j)$$ if $$\alpha$$ is the shortest possible string for which $$\sigma=\alpha\theta_j\omega$$;
$$f(\sigma,N)=(\sigma,N)$$.
$$(3)$$

And finally this is the Algorithm E:
Algorithm E $$(Euclid's \, algorithm)$$. Given two positive integers $$m$$ and $$n$$, find their $$greatest \, common \, divisor$$, that is, the largest positive integer that evenly divides both $$m$$ and $$n$$.
E1. [Find remainder] Divide $$m$$ by $$n$$ and let $$r$$ be the remainder. (We will have $$0 \le r < n$$.)
E2. [Is it zero?] If $$r=0$$, the algorithm terminates; $$n$$ is the answer.
E3. [Reduce] Set $$m \leftarrow n, \, n \leftarrow r$$, and go back to step E1.

I am really happy and I appreciate anyone who comes by and help me because I've spent hours without success in finding the suitable parameters. Thank you StackExchange.

Tags :