Computation of inverses modulo p followup In responding to 
Fast computation of multiplicative inverse modulo q
I mentioned an algorithm for computing the inverse of $a \mod p$ different from the extended Euclidean algorithm, hoping that someone could tell me how its speed stacks up against other algorithms.  Since no one did, I'm asking directly if someone can tell me.
To compute the inverse of a modulo p, you can run the Euclidean algorithm starting with $p^2$ and $ap+1$, comparing the size of each remainder with $p$.  The first remainder less than $p$ that appears will be an inverse for $a \mod p$.  
This will always take either the same number of steps to reach the inverse as it takes to reach $\gcd(a,p)=1$ using the Euclidean algorithm with $a$ and $p$, or else one additional step, depending on whether the least positive residue of an inverse of $a$ is greater than $p/2$ or less than $p/2$.
Thus, it requires approximately the same number of computations as the first half of the extended Euclidean algorithm (albeit with bigger numbers initially), excepting an extra comparison with $p$ at each step.
Question:  How does the speed of this algorithm compare to others?
Aside:  Pedagogically, this is nice since the second half of the extended Euclidean algorithm is the one my students tend to mess up.  However, assuming our ultimate goal is for students to understand why they're doing what they're doing, perhaps the extended Euclidean algorithm is preferable.
 A: Here is a tidy way to solve $ax+by=gcd(a,b)$. Start with the matrix
$$\left(\begin{array}{ccc}
  1&0&a\\
  0&1&b\\
 \end{array}\right)
$$
Suppose $a\ge b$. Then replace row 1 by row 1 minus $t$ times row 2, where $t=\lfloor a/b\rfloor$. Repeat this operation until the last entry in one of the two rows is zero. If the other row is $x,y,d$ then $ax+by=d$ and $d=gcd(a,b)$. This is very simple to program, and avoids the back-substitutions that students find confusing. 
Most of the speedups of the Euclidean Algorithm described in Knuth's Art of Computer Programming v2 work here also.
A: As you mention pedagogy: I solve $a x + b y = \gcd(a,b) $ by simple continued fractions, both by hand and in C++ code. For consecutive convergents $\frac{p_n}{q_n}$ and $\frac{p_{n+1}}{q_{n+1}},$ the standard relation is $p_n  q_{n+1} - p_{n+1} q_n = (-1)^{n+1} $ where the starting point (from Khinchin's little book, Dover reprint) is
$$\frac{p_{-2}}{q_{-2}} = \frac{0}{1} $$ and the fake but necessary
$$\frac{p_{-1}}{q_{-1}} = \frac{1}{0} $$
For a rational number $ \frac{a}{p}$ the final little 2 by 2 determinant may give the wrong sign (and does about half the time), in which case I negate everything.
So, this is the Euclidean algorithm but it all moves forward on the page, no back-substitutions or whatever is in the "second half" of extended gcd. And continued fractions are good for other things.
