0
$\begingroup$

enter image description here

Is it possible to prove using induction? If possible what would be the steps to proof A=B?

Main thing i want to proof is outcome of two segments of code are same.

Below is the code:

Segment A:

int A (int x, int y) {
  if (y==0) return x;
  return A(y, x % y);
}

Segment B:

int B (int x, int y) {
   while (y!=0) {
      int t = y;
      y = x % y;
      x = t;
   }
   return x;
}
$\endgroup$
  • 2
    $\begingroup$ It' enough to prove that both functions indeed compute $gcd(a,b)$ correctly. And then just deduce that they compute the same function. Each function can be easily proved using induction. $\endgroup$ – fade2black Jul 12 '17 at 13:55
  • $\begingroup$ That said, you're looking at the usual recursive/iterative pair. You can show that the N'th iteration of the while-loop corresponds to the N'th call of the recursive function. It's clearly the case for the last iteration (y==0) and it's also the case for every preceding iteration. $\endgroup$ – MSalters Jul 12 '17 at 14:47
  • $\begingroup$ Can i prove like for k=n+1 recursion in segment A and k=n+1 iterations in segment B, result of x and y are the same for both segment? $\endgroup$ – User1234 Jul 13 '17 at 6:22
  • $\begingroup$ Should convert from image to text to enable searching. $\endgroup$ – Apiwat Chantawibul Jul 14 '17 at 13:31
  • $\begingroup$ Cross-posted: cs.stackexchange.com/q/77837/755, math.stackexchange.com/q/2357013/14578. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. $\endgroup$ – D.W. Jul 17 '17 at 6:23
1
$\begingroup$

Proof idea: first of all note that the version A is a recursive version of B. Both A and B halts when $y$ is 0, so in both cases computation lasts until $y$ reaches zero. In both versions the return value is $x$. Also note that each recursive call corresponds to a single step in the while loop. So you can prove that after each recursive call and after each step of the while-loop values of $x$ and $y$ are equals. Induction on the number of steps where we assume $x, y > 0$.

Base step: step 1. In the recursive call (version A) $y$ value is passed as an argument and assigned to $x$ (stored in $x$), but new $y$ takes $x\%y$. In other words, ($x_{new} \leftarrow y_{prev}$ and $y_{new} \leftarrow x_{prev} \% y_{prev}$). Similarly, in the version B the following assignments

int t = y;
y = x % y;
x = t;

implies that $x_{new} \leftarrow y_{prev}$ and $y_{new} \leftarrow x_{prev} \% y_{prev}$. So after the first step in both segments new $x$ and new $y$ values are equal.

Induction: assume that after $n$ steps of recursive call and while-loop $x$ and $y$ values are equal. Then by the same argument as in the Base step for step $n+1$ $x_{new}$ and $y_{new}$ in both codes are equal. Thus, when we $y = 0$ both segments return $x$s which are equal.

Alternatively, you could separately prove that both functions compute gcd of two integers $x$ and $y$ and deduce that they must give the same output for same inputs $x$ and $y$. You can do it yourself. Please look here.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.