Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?
share|improve this question
    
If efficiency is your goal, then shouldn't you modify the Euclidean algorithm to deal with "remainders closest to zero" instead of "negative remainders"? –  Gjergji Zaimi May 3 '12 at 11:34
1  
@Gjergji: I have no efficiency goals and don't intend to use PEA, 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. –  Hans Stricker May 3 '12 at 11:44
    
@Emil: Thanks for the corrections, looks much better now! –  Hans Stricker May 3 '12 at 11:54

3 Answers 3

Your proto-Euclidean algorithm is basically equivalent to the Greedy algorithm for finding the alternating Egyptian fraction representation of a rational. For instance, in your example, if we expand the nested parentheses we get: $$\frac{22}{51} = \frac{1}{2}(1-\frac{1}{7}(1-\frac{1}{25}(1-\frac{1}{51}))) = \frac{1}{2}-\frac{1}{14}+\frac{1}{350}-\frac{1}{17850}$$

UPDATE: This is almost the Fibonacci-Sylvester Algorithm for finding Egyptian Fractions. The difference being that alternating signs between the fractions that the proto-Euclidean algorithm creates. I'm not sure how that affects the rate of convergence and such. You could probably eliminate the sign changes by choosing the signs on the $r_i$ and/or adding/subtracting 1 from each of them. (This is what I had to do for a similar project but can't remember which turned out to give the right answer.) Some heuristics on the F-S method can be found here.

UPDATE #2: Here's a more detailed explanation of the similarity. The Greedy/Fibonacci-Sylvester algorithm can be rephrased to look like a Euclidean-ish Algorithm. Here is the example above: $$ 51 = 3 \cdot 22 - 15$$ $$51 \cdot 3 = 11 \cdot 15 - 12$$ $$51 \cdot 3 \cdot 11 = 141\cdot 12-9$$ $$51\cdot 3 \cdot 11 \cdot 141 = 26367 \cdot 9 - 0$$ so the Greedy/F-S algorithm gives $$\frac{22}{51} = \frac{1}{3}+\frac{1}{11}+\frac{1}{141}+\frac{1}{26367}$$ So the Greedy/F-S algorithm for $a/b$ at the $n$th step is doing a modified division algorithm with $bq_1q_2q_3\cdots q_{n-1}$ as the dividend and $r_{n-1}$ as the divisor (where $q_i$ is the $i$th quotient and $r_i$ is the $i$th remainder) and the Egyptian fraction is given by $\sum 1/q_i$. I say "modified division algorithm" because instead of the usual $b=aq+r$, the $+$ is replaced by a $-$. In your PEA (I think), you just kept the plus.

This is why I conjecture that the heuristics and such are the same. It seems like for every long $a$, $b$ pair in the Greedy/F-S algorithm, there should be an analogous long $a$, $b$ pair for the PEA. I don't have anything at this time other than a gut feeling to back me up. Maybe I'll try to construct an example...

share|improve this answer
    
@Aeryk: Thanks. Do you have a reference, where Euclid's algorithm is discussed as an improvement of the greedy algorithm? –  Hans Stricker May 3 '12 at 13:34
    
@Aeryk's UPDATE: I don't want to change the PE algorithm: it stands like it is, another instance of a family of algorithms of which Euclid's is another - and maybe better - one. The communality is the approach (how to commensurate different quantities), the recursion schema (with $r_i$ replaced by $r_0$), and in the final end two continued expressions which are reciprocally related. –  Hans Stricker May 3 '12 at 17:55
    
@Aeryk: In the meanwhile I have learned that there is nothing like the Egyptian fraction representation, but many. The Greedy algorithm just delivers one. Can you tell me more about the Greedy algorithm for an alternating Egyptian fraction representation? (I guess in general there will be more than one such representation.) –  Hans Stricker May 3 '12 at 23:29

Let me point out that PEA is sometimes considerably "better" and more "to the point" than Fibonacci-Sylvester (see here):

By FS:

$$\frac{5}{91} = \frac{1}{19} + \frac{1}{433} + \frac{1}{249553} + \frac{1}{93414800161} + \frac{1}{17452649778145716451681}$$

$$\frac{5}{121} = \frac{1}{25} + \frac{1}{757} + \frac{1}{763309} + \frac{1}{873960180913} + \frac{1}{1527612795642093418846225}$$

By PEA:

$$\frac{5}{91} = \frac{1}{18} - \frac{1}{1638}$$

$$\frac{5}{121} = \frac{1}{24} - \frac{1}{2904}$$

The claim that PEA is "basically equivalent to the Greedy algorithm" which in turn is "almost the Fibonacci-Sylvester Algorithm" needs further explanation.

share|improve this answer

Sometimes your method is much faster. For the golden ratio $\tau=\frac{1+\sqrt5}{2},$ the Euclidean algorithm gives all quotients $1$ so $[1,1,1,1,1,1,\cdots]$. Your method gives $<1, 2, 4, 17, 19, 5777, 5779, 192900153617, 192900153619, \cdots>$ where the terms after the first appear to come in pairs $\lceil \tau^{2\cdot3^j} \rceil-1,\lceil \tau^{2\cdot3^j} \rceil+1$.

So taking $b,a$ to be successive Fibonacci numbers can sometimes give a large advantage to your method. Actually a ratio of $\tau+1$ is slightly more dramatic. By my calculations $b,a=F_{53},F_{51}=86267571272, 32951280099$ gives $6$ terms $<2,4,17,19,5777,5779>$ vs $51$ terms $[2,1,1,\cdots,1,2]$.

At the other extreme, the Euclidean algorithm gives $[n-1,1,L-1]$ for $\frac{nL-1}{L}.$ It would appear that taking $L=\frac{\mathop{lcm}(1,2,\cdots,n)}{n}$ requires $n-2$ terms for your method. Hence with $n=12$ and $L=2310$ one has for $\frac{27719}{2310}$ the expansions

$[11,1,2309]$ vs $<11, 12, 2519, 2771, 3079, 3464, 3959, 4619, 5543, 6929>.$

share|improve this answer
    
@Aaron: I'd like to give 10 upvotes but can only give one. Do you see a chance to give (general) conditions instead of (extreme) examples? And how to relate such conditions to the algorithms? –  Hans Stricker May 3 '12 at 18:09
    
It seems like cheating, but if the continued fraction has lots of small q values showing up then that speaks against EA being efficient. So quadratic surds may be better for your method. Search Pierce Expansion and Engel Expansion to see what is knownIt is worth remarking that in your expansion the sequence of numbers grows exponentially so in terms of number of digits required to write down it might not be as competitive. –  Aaron Meyerowitz May 3 '12 at 18:47
    
@Aaron: Thanks for the hints to Pierce and Engel - I'll take a trip to Egypt, were Aeryk already has sent me to. (The historical route seems to be from the Egypts to Pythagoras to Euclid and finally to Fibonacci-Sylvester and beyond.) –  Hans Stricker May 3 '12 at 18:58

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.