TAOCP 4.5.2 Exercise 18
Algorithm L already performs several Euclidean divisions at once by using the leading digits of $u$ and $v$.
Section 4.5.2: The Greatest Common Divisor
Exercise 18. [**] [M24] Show how Algorithm L can be extended (as Algorithm A was extended to Algorithm X) to obtain solutions of (15) when $u$ and $v$ are large.
Verified: yes
Solve time: 56s
Algorithm L already performs several Euclidean divisions at once by using the leading digits of $u$ and $v$. To obtain solutions of (15), extend it exactly as Algorithm A was extended to Algorithm X: together with the current pair $(u,v)$, maintain a unimodular transformation matrix
$$ \begin{pmatrix} a&b\ c&d \end{pmatrix}, $$
initially
$$ \begin{pmatrix} 1&0\ 0&1 \end{pmatrix}. $$
Whenever Algorithm L determines a block of quotient steps whose combined effect on $(u,v)$ is
$$ \begin{pmatrix} u'\ v' \end{pmatrix} = \begin{pmatrix} a'&b'\ c'&d' \end{pmatrix} \begin{pmatrix} u\ v \end{pmatrix}, $$
apply the same matrix multiplication to the accumulated coefficient matrix. Thus the matrix always records the linear combinations expressing the current values of $u$ and $v$ in terms of the original inputs.
When Algorithm L terminates with $g=\gcd(u,v)$ and $v=0$, the first row of the accumulated matrix gives
$$ g=a,u_0+b,v_0, $$
where $u_0$ and $v_0$ are the original arguments. Hence $(a,b)$ is a solution of (15). If (15) is the equation
$$ u_0x+v_0y=g, $$
the required solution is therefore
$$ x=a,\qquad y=b. $$
This is precisely the large-integer analogue of the extension from Algorithm A to Algorithm X.