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 : algorithms


Related Questions


Algorithm for Converting Rational Into Surreal Number

Updated November 09, 2017 04:20 AM

Complexity of subset-generation algorithm

Updated August 09, 2015 20:08 PM

Analysis for Karatsuba algorithm for multiplication

Updated September 14, 2017 15:20 PM

How to derive algorithm recurrence?

Updated October 10, 2017 02:20 AM

Approximate Factorization of a Natural Number

Updated November 21, 2017 21:20 PM