Raul Miller <[email protected]> wrote: > Sure, but what was interesting here was that this traversal brought me > to a numerator and denominator which were smaller than the x: result > and yet at the same time had less error than the x: result. > That looks very nice, if it's not just a coincidence. >
It's not a coincidence. From https://en.wikipedia.org/wiki/Stern%E2%80%93Brocot_tree#Mediants_and_binary_search : <https://en.wikipedia.org/wiki/Stern%E2%80%93Brocot_tree> "If a real number *x* is approximated by any rational number *a*/*b* that is not in the sequence of mediants found by the algorithm above, then the sequence of mediants contains a closer approximation to *x* that has a denominator at most equal to *b*; in that sense, these mediants form the best rational approximations <https://en.wikipedia.org/wiki/Best_rational_approximation> to *x*. " <https://en.wikipedia.org/wiki/Stern%E2%80%93Brocot_tree> Of course, no guarantees of speed are provided, only of denominator size relative to error. (It's a little more than just denominator size, but close enough.) Additionally, the tree traversal can be speeded for different classes of problems, depending on how the search object is specified. I mentioned continued fractions as one possible speedup. Raul > -Wm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
