Date: Mar 27, 2000 1:18 AM Author: eppstein@euclid.ics.uci.edu Subject: Re: unitary (Egyptian) fractions

"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 six-term (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 non-greedy

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/