
Re: unitary (Egyptian) fractions
Posted:
Mar 27, 2000 1:18 AM


"r3769" <r3769@calweb.com> writes: > Dan Hoey wrote > > >It took about 13 hours on a 296 Mhz Ultra. > > It could be the algorithm. For example, the following UBASIC program > verifies all a/b [2<=b<=733, 1<=a<b, (a,b)=1] except > {429/431,562/563,640/643,631/647,653/659,732/733} have a sixterm (or less) > expansion in less than 4 MINUTES on my PC.
As Dan wrote earlier, listing all solutions (which his code does) is much slower than sometimes finding one solution (which yours does), finding one solution whenever one exists, or even finding the best solution (e.g. with best = min max denominator).
Looking at your program, it seems it simply applies the greedy algorithm to the fractions m/n  1/x for 100000 choices of x, stops if it gets an expansion with few enough terms, and otherwise gives up. It is clear that this is fast (takes at most 100000 iterations for any number) and works for many values of m/n. I suspect though that there are some short expansions you will never find even if you change the 100000 to your favorite larger number, because they require more than one nongreedy choice.
Dan's code (and some of my code and probably a bunch of other people's code) on the other hand does a recursive backtracking search for solutions  think of a program like yours but with seven nested loops to try multiple choices not only for D0 but also D1, D2, etc  so it's guaranteed not to miss a solution. Of course there are tricks to speed it up, like choosing the number of iterations more intelligently, backtracking when you get a fraction that's going to require too many more terms, or doing something involving factoring when you get down to only two terms, but it will still be slower than code like yours.
Your program has been useful, for finding examples of small fractions which require many terms and for quickly eliminating many other possible examples of small fractions. So don't think you have a bad algorithm for those sorts of tasks, although you might be better off reducing the 100000 to something much smaller (100 or 1000?) and switching to a more powerful method for the values of m/n on which that fails.
I'm also guilty (in a couple of earlier messages in this thread) of comparing my speed to Dan's for code that does different things. But this sort of comparison isn't really fair, because it paints Dan as a bad programmer which is I think not true  he wants more out of his program and is willing to put in the CPU time to get it.  David Eppstein UC Irvine Dept. of Information & Computer Science eppstein@ics.uci.edu http://www.ics.uci.edu/~eppstein/

