Content deleted Content added
eponym at the beginning |
eponym at the beginning |
||
Line 10:
** Decrease ''m'' by one. Let ''x'' be the leading (most significant) digit in ''a'', <math>x=a \text{ div } \beta^m</math> and ''y'' the leading digit in ''b'', <math>y=b \text{ div } \beta^m</math>.
** Initialize a 2 by 3 [[matrix (mathematics)|matrix]] <math>\textstyle \begin{bmatrix} A & B & x\\ C & D & y \end{bmatrix}</math> to an extended [[identity matrix]] <math>\textstyle \begin{bmatrix} 1 & 0 & x \\ 0 & 1 & y\end{bmatrix}</math>, and perform the euclidean algorithm simultaneously on the pairs <math>(x+A,y+C)</math> and <math>(x+B,y+D)</math>, until the quotients differ. That is, iterate:
*** Compute the quotients ''w''<sub>1</sub>
*** If ''w''<sub>1</sub> ≠ ''w''<sub>2</sub>, then break out of the inner iteration. Else set ''w'' to ''w''<sub>1</sub> (or ''w''<sub>2</sub>).
*** Set our current matrix <math>\textstyle \begin{bmatrix} A & B & x \\ C & D & y \end{bmatrix}</math> to <math>\textstyle \begin{bmatrix} 0 & 1 \\ 1 & -w \end{bmatrix} \cdot \begin{bmatrix} A & B & x \\ C & D & y \end{bmatrix} = \begin{bmatrix} C & D &y \\ A - wC & B - wD & x-wy \end{bmatrix}</math>
| |||