Python import Fraction

[gabrielonet]

Hello
Having a programable module like SI5351 I need to compute numerator and denominator from a given value (not static).
For example , x/y= 0.752 , I need to know first plausible integer values for x and y.
In python is was a breeze like from fractions import Fraction then Fraction(0.752) will provide the reverse Euclid computing , but in micropython cannot import Fraction even I add fractions to libraries.
MicroPython v1.19.1 on 2022-06-18; Raspberry Pi Pico with RP2040

Any help please ?
Regards, Gabriel

[rkompass]

# code from https://github.com/alidasdan/best-rational-approximation
def contfr_rat(t):   # best rational approx of t with max denominator 65535 (may be subst. by other N)
    a, b = 1, 0                # initialize the matrix
    c, d = 0, 1
    x, xi = t, int(t)
    while (c*xi + d) <= 65535: # loop finding terms until denom gets too big
        b, a = a, a * xi + b   # multiply these two matrices:
        d, c = c, c * xi + d   #    (a c) and (xi 1)
        if (x == float(xi)):   #    (c d)     (1  0)
            break
        x = 1.0/(x-xi)         # now remaining x is between 0 and 1/xi. Approx as either 0 or 1/m
        xi = int(x)            # where m is max that will fit in 65535.  
    xi = int((65535-d)/c)      # try the other possibility
    p, q = a*xi+b, c*xi+d
    if abs(t-a/c) <= abs(t-p/q):
        return a, c            # first possibility: try zero
    else:
        return p, q

Although it states to be the best approximation, it not necessarily always is. But it's still almost the best.
Good enough for any practial application.
If you want to be perfect:

# from machine import freq

def farey_rat(x, N):
    a, b = 0, 1
    c, d = 1, 1
    while (b <= N and d <= N):
        mediant = (a+c)/(b+d)
        if x == mediant:
            if b + d <= N:
                return a+c, b+d
            elif d > b:
                return c, d
            else:
                return a, b
        elif x > mediant:
            a, b = a+c, b+d
        else:
            c, d = a+c, b+d

    if (b > N):
        return c, d
    else:
        return a, b

def contfr_rat(t, N):    # N is upper bound for denominator
    p0, p1 = 1, 0
    q0, q1 = 0, 1        
    x = t
    while True:          # compute new (p0 / q0) ratio from old ratio (p1 / q1)
        ai = int(x)
        qx = q0*ai + q1
        if qx >= N:      # break if new denominator will be too big
            break
        p0, p1 = p0 * ai + p1, p0
        q0, q1 = qx, q0
        if (x == float(ai)):
            return p0, q0
        x = 1.0/(x-ai)
    ai = int((N-q1)/q0)  # try the other possibility
    p, q = p0*ai+p1, q0*ai+q1
    if abs(t-p0/q0) <= abs(t-p/q):
        return p0, q0
    else:
        return p, q

# this gives better rational approximations than farey_rat() and contfr_rat(), but we need double precision
#  https://shreevatsa.wordpress.com/2011/01/10/not-all-best-rational-approximations-are-the-convergents-of-the-continued-fraction/
def contfr_rat2(t, N):   # N now is upper bound on denominator (1 + max denom.)
    p0, p1 = 1, 0 
    q0, q1 = 0, 1        
    x = t
    while True:          # compute new (p0 / q0) ratio from old ratio (p1 / q1)
        ai = int(x)
        qx = q0*ai + q1
        if qx >= N:      # break if new denominator will be too big
            break
        p0, p1 = p0 * ai + p1, p0
        q0, q1 = qx, q0
        if (x == float(ai)):
            return p0, q0
        x = 1.0/(x-ai)
    n = int((N-q1-1)/q0)  # largest n so that n*q0+q1 < N
    if n >= ai//2:  # we check, if we can use p, q = n*p0+p1, n*q0+q1 for n >= ai//2
        p, q = n*p0+p1, n*q0+q1
        if n >= ai//2 + 1 or n == ai//2 and abs(t-p/q) < abs(t-p0/q0):
            return p, q
    return p0, q0

for x in range(100):
    x =x/100+0.001336
    p1,q1 = farey_rat(x, 65535)
    p2, q2 = contfr_rat(x, 65535)
    print('x:', x, 'farey:', p1,'/', q1, abs(x-p1/q1), 'contfr:', p2,'/', q2, abs(x-p2/q2))

[gabrielonet]

## thanks rkompass ! 
IF (  I do not master math == TRUE)  :
      Got to go back to primary school 
else :
    print ("Many thanks ! ") 
### anyways , 
print ("From open source, great power comes, much obliged !")     
## reverse Euclid should not be computed via loops, otherwise I could write  a loop until first numerator and denominator comes to life
## but it comes with computing wasted time
## should be as in indexed array from back times  math already computed values
## Regards , Gabriel YO8RXP

[gabrielonet]

sorry for bold text, never posted upon github discussions

[jimmo]

sorry for bold text, never posted upon github discussions

Fixed. See the welcome post -- #9111 -- for formatting tips.

but in micropython cannot import Fraction even I add fractions to libraries.

Can you explain what you mean by this?