Proto-Euclidean algorithm - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-18T21:26:38Z http://mathoverflow.net/feeds/question/95843 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/95843/proto-euclidean-algorithm Proto-Euclidean algorithm Hans Stricker 2012-05-03T11:05:15Z 2012-05-04T03:40:06Z <p>Consider the <strong><a href="http://en.wikipedia.org/wiki/Euclidean_algorithm" rel="nofollow">Euclidean algorithm</a> (EA)</strong> as a way to measure the relative length $b/a$ of a shorter stick $b$ compared to a longer one $a$ by recursively determining </p> <p>$$q_i = \left\lfloor \frac{r_i}{r_{i+1}} \right\rfloor\qquad (*)$$</p> <p>$$r_{i+2} = r_i\bmod r_{i+1}$$</p> <p>with $r_0 = a$, $r_1 = b$. The relative length $b/a$ is then given by the (finite or infinite) continued fraction </p> <p>$$\cfrac{1}{q_0 + \cfrac{1}{q_1 + \cfrac{1}{q_2 + \cfrac{1}{\ddots }}}} =:\ [ q_0, q_1, q_2, \ldots ]^{-1}$$</p> <p>A rather similar and somehow simpler algorithm is the following which I call <strong>proto-Euclidean algorithm (PEA)</strong>:</p> <p>$$q_i = \left\lfloor \frac{r_0}{r_{i+1}} \right\rfloor$$</p> <p>$$r_{i+2} = r_0\bmod r_{i+1}$$</p> <p>The relative length $b/a$ is then given by the (finite or infinite) continued product</p> <p>$$\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$$</p> <p>[<strong>Update:</strong> 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$.]</p> <p>For comparisonâ€™s sake, with $a=1071$, $b=462$ , the Euclidean algorithm yields </p> <p>$$[2, 3, 7]^{-1} = \cfrac{1}{2 + \cfrac{1}{3 + \cfrac{1}{7}}} = \frac{22}{51}$$</p> <p>while the proto-Euclidean algorithm yields </p> <p>$$\langle2,7,25,51\rangle = \frac{1}{2}(1- \frac{1}{7}(1- \frac{1}{25}(1-\frac{1}{51}))) = \frac{22}{51}$$.</p> <blockquote> <p>Under which name is the proto-Euclidean algorithm known? Where is it investigated and compared to the Euclidean algorithm? Or is it just folklore?</p> </blockquote> <p>I am especially interested in the following questions:</p> <blockquote> <ul> <li>How fast does PEA converge compared to EA?</li> </ul> </blockquote> <p>(Just a side note: the first approximations in the sample above are equal: $[2, 3]^{-1} = \frac{3}{7} = \langle2,7\rangle$).</p> <p>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.</p> <blockquote> <ul> <li>Is PEA significantly less efficient than EA?</li> </ul> </blockquote> http://mathoverflow.net/questions/95843/proto-euclidean-algorithm/95864#95864 Answer by Aeryk for Proto-Euclidean algorithm Aeryk 2012-05-03T13:26:29Z 2012-05-04T03:40:06Z <p>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}$$</p> <p>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 <a href="http://books.google.com/books?id=HBzXEHGq5wMC&amp;pg=PA207&amp;lpg=PA207&amp;dq=Fibonacci-Sylvester+Algorithm&amp;source=bl&amp;ots=O7LBf669ya&amp;sig=H8tNhwobH1gsqTtkerNj0UqMB3U&amp;hl=en&amp;sa=X&amp;ei=OZyiT5iQLM7dgQe9tOn6CA&amp;ved=0CEUQ6AEwBA" rel="nofollow">here</a>.</p> <p>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.</p> <p>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...</p> http://mathoverflow.net/questions/95843/proto-euclidean-algorithm/95903#95903 Answer by Aaron Meyerowitz for Proto-Euclidean algorithm Aaron Meyerowitz 2012-05-03T18:03:31Z 2012-05-03T18:03:31Z <p>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 $&lt;1, 2, 4, 17, 19, 5777, 5779, 192900153617, 192900153619, \cdots>$ where the terms after the first <a href="http://oeis.org/A001999" rel="nofollow">appear</a> to come in pairs $\lceil \tau^{2\cdot3^j} \rceil-1,\lceil \tau^{2\cdot3^j} \rceil+1$. </p> <p>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 $&lt;2,4,17,19,5777,5779>$ vs $51$ terms $[2,1,1,\cdots,1,2]$. </p> <p>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 </p> <p>$[11,1,2309]$ vs $&lt;11, 12, 2519, 2771, 3079, 3464, 3959, 4619, 5543, 6929>.$</p> http://mathoverflow.net/questions/95843/proto-euclidean-algorithm/95932#95932 Answer by Hans Stricker for Proto-Euclidean algorithm Hans Stricker 2012-05-03T23:19:55Z 2012-05-03T23:19:55Z <p>Let me point out that PEA is sometimes considerably "better" and more "to the point" than Fibonacci-Sylvester (see <a href="http://books.google.de/books?id=HBzXEHGq5wMC&amp;lpg=PA207&amp;ots=O7LBf669ya&amp;dq=Fibonacci-Sylvester%2520Algorithm&amp;pg=PA209#v=onepage&amp;q=Fibonacci-Sylvester%2520Algorithm&amp;f=false" rel="nofollow">here</a>):</p> <p>By FS:</p> <p>$$\frac{5}{91} = \frac{1}{19} + \frac{1}{433} + \frac{1}{249553} + \frac{1}{93414800161} + \frac{1}{17452649778145716451681}$$</p> <p>$$\frac{5}{121} = \frac{1}{25} + \frac{1}{757} + \frac{1}{763309} + \frac{1}{873960180913} + \frac{1}{1527612795642093418846225}$$</p> <p>By PEA:</p> <p>$$\frac{5}{91} = \frac{1}{18} - \frac{1}{1638}$$</p> <p>$$\frac{5}{121} = \frac{1}{24} - \frac{1}{2904}$$</p> <p>The claim that PEA is "basically equivalent to the Greedy algorithm" which in turn is "almost the Fibonacci-Sylvester Algorithm" needs further explanation.</p>