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.

- ServerfaultXchanger
- SuperuserXchanger
- UbuntuXchanger
- WebappsXchanger
- WebmastersXchanger
- ProgrammersXchanger
- DbaXchanger
- DrupalXchanger
- WordpressXchanger
- MagentoXchanger
- JoomlaXchanger
- AndroidXchanger
- AppleXchanger
- GameXchanger
- GamingXchanger
- BlenderXchanger
- UxXchanger
- CookingXchanger
- PhotoXchanger
- StatsXchanger
- MathXchanger
- DiyXchanger
- GisXchanger
- TexXchanger
- MetaXchanger
- ElectronicsXchanger
- StackoverflowXchanger
- BitcoinXchanger
- EthereumXcanger