Re: Bit fiddling calculating fraction

"Ben Bacarisse" <ben.usenet@xxxxxxxxx> wrote in message
news:87d55rvjps.fsf@xxxxxxxxxxxx

Eh? What did I miss? The OP starts with a known rational
valueA * valueB over 31 and CBF posts code to find a rational close
to a given double. How does it help? The original rational even has
a prime denominator so it can't even be reduced -- it's as good as
he'll get (if a rational is what he wants).

Oh, OK, I may have missed some of the nuances of the original post.

In the larger scheme of things, just let me make the observation that these
two problems are functionally equivalent.

a)Finding a best rational approximation, with a certain maximum numerator
and denominator, to a constant that is irrational.

b)Finding a best rational approximation, with a certain maximum numerator
and denominator, to a constant that is rational but that can't be expressed
exactly without exceeding that certain maximum numerator and denominator.

For example, the conversion constant from MPH to KPH is 1.609344 (I think
this comes from the NIST or someone who should know). This constant is
rational, but can't be expressed with numerator and denominator not
exceeding 255 (for example).

Using the continued fraction technique to find the best approximation with
numerator and denominator not exceeding 255 (output pasted in at end) yields
103/64 as the best approximation.

103/64 is 1.609375 (pretty close). (By the way, it is sheer coincidence
that the denominator came out to be a power of 2).

Chuck's code has merit and relevance precisely in this situation. With
Chuck's program, one would input the rational constant (1.609344) and get an
approximation that could be expressed with smaller numerator and
denominator. The "double" in Chuck's program may be in fact rational but
just not expressible under the constraints on the numerator and denominator.

My observation was that the math driving Chuck's program seemed to be ad hoc
and probably O(N). That won't work well for approximations in, say, 256
bits.

But the idea is sound. "Rational" and "rational under computational
constraints" are two different things.

Dave.

----------

C:\Documents and Settings\dashley>cfbrapab 1.609344 255 255
------------------------------------------------------------------------------
MAJOR MODE: Finding closest rational number(s) under the constraints.
------------------------------------------------------------------------------
RI_IN Numerator: 25,146 ( 5
digits)
------------------------------------------------------------------------------
RI_IN Denominator: 15,625 ( 5
digits)
------------------------------------------------------------------------------
K_MAX: 255 ( 3
digits)
------------------------------------------------------------------------------
H_MAX: 255 ( 3
digits)
------------------------------------------------------------------------------
approx_num(1): 103 ( 3
digits)
------------------------------------------------------------------------------
approx_den(1): 64 ( 2
digits)
------------------------------------------------------------------------------
dap_num(1): 1, ( 109
digits)
609,375,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000
------------------------------------------------------------------------------
dap_den(1): 1, ( 109
digits)
000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000
------------------------------------------------------------------------------
error_num(1): 31 ( 2
digits)
------------------------------------------------------------------------------
error_den(1): 1,000,000 ( 7
digits)
------------------------------------------------------------------------------


.

Relevant Pages

  • Re: ratio approximation algorithm
    ... The numerator and denominator are each of the form a*b, ... That reduces to finding a rational approximation to ... Modify it to input the value you ...
    (comp.programming)
  • Re: math and logic problem
    ... You have nine digits. ... than the numerator but less than ten times the numerator. ... numerator must have four digits and the denominator five. ... multiple of 3, so by difference the numerator must have a digit sum ...
    (sci.math)
  • Re: Rational numbers
    ... > where the numerator is the decimal part of the original number, ... > denominator is a one followed by N zeros (the same number of zeros as the ... > numerator has digits). ... > where the denominator has N nines. ...
    (sci.math)
  • Re: float("nan") in set or as key
    ... floating point, and you define a function that uses Newton's ... The numerator and denominator get very big, ... the number of digits in numerator and denominator ...
    (comp.lang.python)
  • Re: pi value
    ... approximation, though. ... p and q are the numerator and denominator of a rational number p/q ...
    (sci.math)