Content deleted Content added
eponym at the beginning |
|||
Line 7:
* If ''b'' contains only one digit (in the chosen [[radix|base]], say <math>\beta=1000</math> or <math>\beta=2^{32}</math>), use some other method, such as the [[Euclidean algorithm]], to obtain the result.
* If ''a'' and ''b'' differ in the length of digits, perform a division so that ''a'' and ''b'' are equal in length, with length equal to ''m''.
* Iterate until one of ''a'' or ''b'' is zero:
** 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> of the long divisions of (''x'' + ''A'') by (''y'' + ''C'') and ''w''<sub>2</sub> of (''x'' + ''B'') by (''y'' + ''D'') respectively. Also let ''w'' be the (not computed) quotient from the current long division in the chain of long divisions of the euclidean algorithm.
*** 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
*** 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>▼
::::<math>\textstyle \begin{bmatrix} A & B & x \\ C & D & y \end{bmatrix}</math>
to
▲
*** If ''B'' = 0, we have reached a ''deadlock''; perform a normal step of the euclidean algorithm with ''a'' and ''b'', and recompute the matrix.
** Set ''a'' to ''aA'' + ''bB'' and ''b'' to ''Ca'' + ''Db'' (again simultaneously). This applies the steps of the euclidean algorithm that were performed on the leading digits in compressed form to the long integers ''a'' and ''b''. Restart the outer iteration.
| |||