def formal_fractional_part(R):
    "calculates the polynomial part of a rational function"
    return R - polynomial_part(R)

def polynomial_part(R):
    "calculates the fractional part of a rational function"
    f = R.numerator()
    g = R.denominator()
    a=f.quo_rem(g)
    return a[0]

def formal_adic_expansion(R,precision,B):
    "calculates the adic of a rational function"
    "input: a rational function R, an integer precision, and a polynomial B"
    "output: the base-B expansion of R up to precision"
    S = polynomial_part(R)
    expansion = []
    #while(R!=S) and S.degree()<=1:
    counter = 0
    while(R!=S and counter < precision):
        expansion.append(S)
        R = (R-S)*B
        S = polynomial_part(R)
        counter+=1
    #if S.degree()<=1:
    #    cfe.append(S)
    expansion.append(S)
    return expansion

def formal_continued_fraction(R):
    "calculates the continued fraction expansion of a rational function"
    "input: a rational function R"
    "output: the continued fraction expansion of R"
    S = polynomial_part(R)
    cfe = []
    #while(R!=S) and S.degree()<=1:
    while(R!=S):
        cfe.append(S)
        R = 1/(R - S)
        S = polynomial_part(R)
    #if S.degree()<=1:
    #    cfe.append(S)
    cfe.append(S)
    return cfe

def nikita_expansion(R):
    "calculates the shulga decomposition of a rational function"
    "input: a rational function R"
    "output: the continued fraction expansions of x and y that are given by the shulga decomposition and satisfy such that x+y=R"
    x=0
    cfe1 = [0]
    S = polynomial_part(R)
    cfe2 = [S]
    y=S
    #while(R!=S) and S.degree()<=1:
    counter = 1
    while(R!=x+y):
        temp_cfe = formal_continued_fraction(R-y)
        #print(temp_cfe[counter],counter)
        cfe1.append(temp_cfe[counter])
        x=formal_continued_fraction_inverse(cfe1)
        if R==x+y:
            break
        else:
            temp_cfe = formal_continued_fraction(R-x)
            cfe2.append(temp_cfe[counter])
            y=formal_continued_fraction_inverse(cfe2)
            #print(temp_cfe[counter],counter)
        counter+=1
    return cfe1,cfe2

def formal_continued_fraction_inverse(cfe):
    "calculates the rational function from its continued fraction expansion"
    "input: a list of polynomials cfe"
    "output: a rational function R whose cfe is the input"
    leng=len(cfe)
    R=cfe[leng-1]
    for i in range(leng-2,-1,-1):
        R=1/R
        R += cfe[i]
    return R

def best_denominators(cfe):
    "calculates the best denominators of a rational function with a given continued fraction expansion"
    "input: a list of polynomials cfe"
    "output: a list of denominators of the convergents of the rational function whose cfe is given"
    l=len(cfe)
    q = [1]*l
    q[1] = cfe[1]
    for i in range(2,l):
        q[i] = cfe[i]*q[i-1]+q[i-2]
    return q

def get_degrees(cfe):
    "outputs the degrees of the partial quotients in a list apart from the zeroth partial quotient"
    degrees=[]
    for partial_quotient in cfe[1:]:
        if (partial_quotient != 0):
            degrees.append(partial_quotient.degree())
    
    return degrees

char = 2
n = 1
fieldSize = char^n
H = 10

if char!=0:
    s=GF(fieldSize)
else:
    s=QQ

F.<t> = s[]

cfe1 = [0,t,t^5,t^9,t^13,t^17,t^21,t^25,t^29]
cfe2 = [0,t^3,t^7,t^11,t^15,t^19,t^23,t^27,t^31]
series1 = formal_continued_fraction_inverse(cfe1)
series2 = formal_continued_fraction_inverse(cfe2)
series = series1 + series2
cfe = formal_continued_fraction(series)

h=10
cfe=[0]+[t]*h
series = formal_continued_fraction_inverse(cfe)
print(series)
print(cfe)

[cfe1,cfe2]=nikita_expansion(series)
print(cfe1)
print(cfe2)
print(get_degrees(cfe1))
print(get_degrees(cfe2))