gud_day's blog

Iterative GCD function to find GCD coefficients
By gud_day, history, 5 years ago, In English

Hi!

I was hoping someone could help me understand how this bit of code works written by saeed_odak in this submission to 1117E : code:

  • int mul_inv(int a, int b) { //Returns multiplicative inverse of a wrt b
  • int b0 = b, t, q;
  • int x0 = 0, x1 = 1;
  • if (b == 1) return 1;
  • while (a > 1) {
  • q = a / b;
  • t = b, b = a % b, a = t;
  • t = x0, x0 = x1 - q * x0, x1 = t;
  • }
  • if (x1 < 0) x1 += b0;
  • return x1;
  • } ``
  • I think understanding how to write an iterative GCD function that develops GCD coeffecients would be helpful to understand this piece of code, but I can't seem to come up with a way to do so and online searches only provide code and not good explanations.

Any help would be appreciated.

Thank you!

EDIT: Resolved. Looks like there were actually sources that explained that algorithm well that I missed. The wikipedia page Wikipedia itself details the algorithm quite well. Looks like I posted prematurely without doing enough searching on my part.

Sorry!

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by grandesonnerie (previous revision, new revision, compare).

→ Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I just want to add that the recursive version is much easier to understand and derive (in my opinion).

You can read about it here

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for linking, the post was really helpful!

    → Reply