"Bald Eagle" <cre### [at] netscapenet> wrote:
> "Tor Olav Kristensen" <tor### [at] TOBEREMOVEDgmailcom> wrote:
> > "Bald Eagle" <cre### [at] netscapenet> wrote:
> > > "Tor Olav Kristensen" <tor### [at] TOBEREMOVEDgmailcom> wrote:
> > > ...  I would also like to figure out if there's a nice
> > > degrees-to-fractions-of-pi algorithm out there, and I could implement that.
> > > I'll probably just hard-code an array of text objects.
> >
> > You can divide the angle by 180 and convert the resulting decimal number to a
> > fraction. Then you can use David Eppstein's "find rational approximation to
> > given real number" code as suggested in the first answer here:
> >
> >
https://stackoverflow.com/questions/95727/how-to-convert-floats-to-human-readable-fractions
>
>
> I tried at least 2 different ways to go about this, but I didn't have any
> success and fell into some kind of trap in the recursion programming that
> short-circuits things.   It was a mess that I spent too many hours trying to
> fix.
>
> I have more application cases that I'd like to apply this sort of thing to, if
> you give me a nudge in the proper direction.

Hi

As I know that you are very fond of Python, I'll nudge you to have a
look this code (which SEEMS to work ok):


# real_num: real number to approximate
# max_denom: maximum denominator allowed

def real_to_fraction(real_num, max_denom):

    max_int = 2**31 - 1  # LONG_MAX == 0x7FFFFFFF in C
    x = real_num
    max_denom = int(max_denom)
    m00 = int(1)
    m01 = int(0)
    m10 = int(0)
    m11 = int(1)

    # loop finding terms until denominator gets too big
    ai = int(x)
    while (m10*ai + m11 <= max_denom):
        tmp = m00*ai + m01
        m01 = int(m00)
        m00 = int(tmp)
        tmp = m10*ai + m11
        m11 = int(m10)
        m10 = int(tmp)
        if (x == ai):
            break  # AF: division by zero
        x = 1/(x - ai)
        if (abs(x) > max_int):
            break  # AF: representation failure
        ai = int(x)

    # now remaining x is between 0 and 1/ai
    # approximate as either 0 or 1/m where
    # m is max that will fit in max_denom

    # first try zero
    error = real_num - m00/m10
    print(f'{m00}/{m10}, error = {error}\n')

    # then try other possibility
    ai = int((max_denom - m11)/m10)
    m00 = int(m00*ai + m01)
    m10 = int(m10*ai + m11)
    error = real_num - m00/m10
    print(f'{m00}/{m10}, error = {error}\n')


Test run:

    real_to_fraction(3.875, 100)

    31/8, error = 0.0

    376/97, error = -0.0012886597938144284


The type long in C is the same as the type signed long int.
So I put  int() around every expression going into variables
of type long.

As you know, I don't like break statements in loops, so this
remains to be fixed.

In Python max_int should probably be chosen to be maxsize or
maxsize - 1 (after doing "from sys import maxsize").


--
Tor Olav
http://subcube.com
https://github.com/t-o-k

Post a reply to this message