Consider the **Euclidean algorithm (EA)** as a way to measure the relative length $b/a$ of a shorter stick $b$ compared to a longer one $a$ by recursively determining

$$q_i = \left\lfloor \frac{r_i}{r_{i+1}} \right\rfloor\qquad (*)$$

$$r_{i+2} = r_i\bmod r_{i+1} $$

with $r_0 = a$, $r_1 = b$. The relative length $b/a$ is then given by the (finite or infinite) continued fraction

$$\cfrac{1}{q_0 + \cfrac{1}{q_1 + \cfrac{1}{q_2 + \cfrac{1}{\ddots }}}} =:\ [ q_0, q_1, q_2, \ldots ]^{-1}$$

A rather similar and somehow simpler algorithm is the following which I call **proto-Euclidean algorithm (PEA)**:

$$q_i = \left\lfloor \frac{r_0}{r_{i+1}} \right\rfloor $$

$$r_{i+2} = r_0\bmod r_{i+1} $$

The relative length $b/a$ is then given by the (finite or infinite) continued product

$$\frac{1}{q_0}(1- \frac{1}{q_1}(1- \frac{1}{q_2}(1-\cdots))) =:\ \langle q_0, q_1, q_2, \ldots \rangle$$

[**Update:** The one and crucial difference between the two algorithms is the numerator in $(*)$ which represents the reference length against which the current "remainder" is measured: in EA it is adjusted in every step to the last "remainder", in PEA it is held fixed to $r_0$.]

For comparison’s sake, with $a=1071$, $b=462$ , the Euclidean algorithm yields

$$[2, 3, 7]^{-1} = \cfrac{1}{2 + \cfrac{1}{3 + \cfrac{1}{7}}} = \frac{22}{51} $$

while the proto-Euclidean algorithm yields

$$\langle2,7,25,51\rangle = \frac{1}{2}(1- \frac{1}{7}(1- \frac{1}{25}(1-\frac{1}{51}))) = \frac{22}{51} $$.

Under which name is the proto-Euclidean algorithm known? Where is it investigated and compared to the Euclidean algorithm? Or is it just folklore?

I am especially interested in the following questions:

- How fast does PEA converge compared to EA?

(Just a side note: the first approximations in the sample above are equal: $[2, 3]^{-1} = \frac{3}{7} = \langle2,7\rangle $).

One advantage of EA over PEA seems to be that it takes fewer steps, and smaller numbers are involved in the course of calculation, since the numerator in $(*)$ decreases.

- Is PEA significantly less efficient than EA?

usePEA, just hoped to understand EA even better, eventually, by comparing it to PEA. Where do you see negative remainders? PEA's remainders go as close to zero as possible, at least closer than EA's. $\endgroup$ – Hans-Peter Stricker May 3 '12 at 11:44