Comment #21 on issue 4122 by lucasbro...@gmail.com: Egyptian fractions
http://code.google.com/p/sympy/issues/detail?id=4122
Limits on the greedy / Fibonacci-Sylvester algorithm:
* Given *p/q* in lowest terms, generates an expansion of maximum length *p*.
Even as the numerators get large, the number of terms is seldom more than
a handful.
* Uses minimal memory.
* Only potential problem is that the terms can blow up (standard examples
of this are 5/121 and 31/311); however, this isn't really a problem in
Python until the numbers reach obscenely large numbers of digits. The
denominator is at most squared at each step (doubly-exponential growth) and
typically exhibits singly-exponential growth.
Limits on Golomb's algorithm:
* As in the code, let *modinv(a,b)* return the multiplicative inverse
of *a*with respect to
*b*.
* Suppose we input a fraction *x/y* in lowest terms. Then the largest
denominator in the expansion is *y * modinv(x,y)*.
* The length of the expansion at most *x* (this occurs when *x == y-1*).
I'm still trying to figure out if there's an exact, compact formula that
relates the inputs to the number of terms in the output, but this method
could hog resources as the inputs get close to 1.
Limits on the Engel algorithm:
* Given *p/q* in lowest terms, the number of terms in the Engel expansion
is on the order of *∛q* (Erdös & Shallit, 1991:
http://archive.numdam.org/ARCHIVE/JTNB/JTNB_1991__3_1/JTNB_1991__3_1_43_0/JTNB_1991__3_1_43_0.pdf
).
* Quoting Wikipedia: "The sequence *a_n* of Engel multipliers will
typically exhibit exponential growth. More precisely, for almost all
numbers in the interval *(0,1]*, the limit as *n*→*∞* of *a_n^(1/n)* exists
and is equal to *e*." The terms of the Engel expansion itself will
therefore tend to grow doubly-exponentially.
* Due to the way the Engel multipliers are obtained and combined into the
Engel expansion, I would be very surprised if this generated problems like
the Graham-Jewett and Takenouchi methods demonstrated except for obscenely
large inputs.
Limits on the binary algorithm:
* Apparently the proper name is "binary remainder".
* Given x/y in lowest terms, the method produces at most Log2(x) + Log2(y)
terms; in practice it will typically produce half that many.
* Each denominator is at most *y^2*.
--
You received this message because this project is configured to send all
issue notifications to this address.
You may adjust your notification preferences at:
https://code.google.com/hosting/settings
--
You received this message because you are subscribed to the Google Groups
"sympy-issues" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sympy-issues+unsubscr...@googlegroups.com.
To post to this group, send email to sympy-issues@googlegroups.com.
Visit this group at http://groups.google.com/group/sympy-issues.
For more options, visit https://groups.google.com/groups/opt_out.
