Return to Question

edited body

view source

edited May 3 2012 at 18:44

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] 3]^{-1} = \frac{7}{3} frac{3}{7} = \langle2,7\rangle^{-1} 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?

added 283 characters in body

view source

edited May 3 2012 at 18:39

Hans Stricker
5,392●13●39

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 (inverse of the) relative length $b/a$ is then given by the (finite or infinite) continued fraction

$$q_0 $\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$$

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] = \frac{7}{3} = \langle2,7\rangle^{-1} $).

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?

added 16 characters in body

view source

edited May 3 2012 at 13:59

Hans Stricker
5,392●13●39

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 (inverse of the) relative length $b/a$ is then given by the (finite or infinite) continued fraction

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

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$$

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

$$[2, 3, 7] 7]^{-1} = 2 \cfrac{1}{2 + \cfrac{1}{3 + \cfrac{1}{7}} cfrac{1}{7}}} = \frac{51}{22} 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] = \frac{7}{3} = \langle2,7\rangle^{-1} $).

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?

fix angle brackets and other typographic issues

view source

edited May 3 2012 at 11:49

Emil Jeřábek
10.8k●1●27●42

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 = \lfloor left\lfloor \frac{r_i}{r_{i+1}} \rfloor\ \ \\ right\rfloor\qquad (*)$$

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

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

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

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

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

$$r_{i+2} = r_0\mod 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-\ldots))) frac{1}{q_2}(1-\cdots))) =:\ < \langle q_0, q_1, q_2, \ldots >$$\rangle$$

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

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

while the proto-Euclidean algorithm yields

$<2,7,25,51> $\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] = \frac{7}{3} = <2,7>^{-1} \langle2,7\rangle^{-1} $).

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?

view source

asked May 3 2012 at 11:05

Hans Stricker
5,392●13●39

Proto-Euclidean algorithm

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 = \lfloor \frac{r_i}{r_{i+1}} \rfloor\ \ \ \ (*)$$

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

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

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

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

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

$$r_{i+2} = r_0\mod 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-\ldots))) =:\ < q_0, q_1, q_2, \ldots >$$

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

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

while the proto-Euclidean algorithm yields

$$<2,7,25,51> = \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] = \frac{7}{3} = <2,7>^{-1} $).

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?