I have posted this question at stackexchange (502413), without responses until now.
In the papers by T. Motzkin: The Euclidean Algorithm, Bull. AMS 55, 1949, pp. 1142--1146 and P. Samuel: About Euclidean Rings, Journ. of Alg. 19, 1971, pp. 282--301, it is shown that among all the Euclidean algorithms on a given domain (wlog: taking values in one fixed well-ordered set), there is a unique smallest one in the sense that it takes smallest values. In fact, it is the pointwise infimum of all Euclidean algorithms. Samuel just calls this the "smallest" algorithm, but Motzkin calls it the "fastest" algorithm and remarks on "faster" algorithms (p. 1142/3):
(under certain additional conditions, indeed less algorithm steps are needed).
This remark confuses me. The following is my attempt to interpret it, which leads to two questions.
I assume that by "algorithm steps" we are talking about the classical application of the Euclidean algorithm, namely, to compute gcd's. (Maybe this is already a complete misinterpretation, but I do not know what else "algorithm steps" could refer to.) So say we have two elements $a,b$ of a ring which is Euclidean with respect to several norms. Let us take these norms as $\mathbb{N}_0$-valued as in the classical definition. If we want to find a $\gcd(a,b)$, we can use any Euclidean algorithm. Now the following observation is nearly trivial: Using a Euclidean algorithm w.r.t. a norm $|\cdot|$, at most $\min (|a|, |b|) (\pm 1$, according to conventions) steps are needed to arrive at a gcd, because at each step, the norm of the divisor is strictly smaller than that of the divisor of the previous step. So when we have $|\cdot |_1 \le | \cdot |_2$ in the sense of Motzkin and Samuel, we can expect a tendency that using $|\cdot|_1$ might need less algorithm steps to arrive at a gcd.
Question: Beyond this tendency, can we say anything specific? That is, what might Motzkin have in mind as "certain additional conditions"?
There is a complication which should be resolved before: Even if we use only one Euclidean norm, usually there is no uniqueness assumption about the divisor and remainder term, and choosing them differently leads to varying numbers of steps.
Easy example: The ring of integers $\mathbb{Z}$ is Euclidean w.r.t. the usual absolute value. To compute $\gcd(8,3)$, we can go through
$8 = 2 \cdot 3 + 2$
$3 = 1 \cdot 2 + 1$
$2 = 2 \cdot 1 + 0$
but we need one step less with
$8 = 3 \cdot 3 + (-1)$
$3 = -3 \cdot (-1) + 0$.
One obvious guess is that in each division-with-remainder step, one takes a smallest among all possible remainders -- like in the example, where $|-1| < |2|$. Motzkin seems to suggest this in the 2nd paragraph on p. 1144. I think I have an ad hoc argument why this works for the ring $\mathbb{Z}$, but I do not see a general principle.
Question for starters: For a fixed Euclidean norm, is it true that taking a minimal remainder in each step leads to a minimal number of steps (for this norm)?
Added: A colleague has turned my attention to this arxiv post from which I have learned that Kronecker had predated my "ad hoc argument" and given a positive answer to the 2nd question for $(\mathbb{Z}, | \cdot |)$; an elaboration of which can be found in A. W. Goodman, W. M. Zaring: Euclid's Algorithm and the Least-Remainder Algorithm, Amer. Math. Monthly 59 (1952), pp. 156-159. Searching through citations of this, no one in that camp seems to have investigated other Euclidean domains than $(\mathbb{Z}, | \cdot |)$.
