Toy GCD

gcd_toy.py

nbits = 3

def encode(l):
    retval = {}
    for a in l:
        tmp = 0
        for i in range(len(a)):
               tmp += a[i] << (nbits * i)
        retval[tmp] = l[a]
    return retval

def decode(l,nvars):
    retval = {}
    for a in l:
        tmp = []
        tmp_val = type(a)(a)
        for i in range(nvars):
            r = tmp_val % (2**nbits)
            tmp.append(r)
            tmp_val = (tmp_val - r) >> nbits
        tmp = tuple(tmp)
        retval[tmp] = l[a]
    return retval

def lterm(l):
    m = max(l)
    return m,l[m]

def add(a,b):
    retval = dict(a)
    for t in b:
        if t in a:
            retval[t] += b[t]
            if retval[t] == 0:
                del retval[t]
        else:
            retval[t] = b[t]
    return retval

def sub(a,b):
    retval = dict(a)
    for t in b:
        if t in a:
            retval[t] -= b[t]
            if retval[t] == 0:
                del retval[t]
        else:
            retval[t] = -b[t]
    return retval

def mul(a,b):
    retval = {}
    for n in a:
        for m in b:
            e = n + m
            if e in retval:
                retval[e] += a[n]*b[m]
                if retval[e] == 0:
                    del retval[e]
            else:
                retval[e] = a[n]*b[m]
    return retval

def scalmul(a,p):
    if a == 0:
        return {}
    p = dict(p)
    for t in p:
        p[t] *= a
    return p

def scaldiv(p,a):
    p = dict(p)
    for t in p:
        p[t] /= a
    return p

def ldiv(num,den):
    q, r = {}, dict(num)
    while len(r) != 0 and lterm(r)[0] >= lterm(den)[0]:
        #print('*')
        t = {lterm(r)[0]-lterm(den)[0]:lterm(r)[1]/lterm(den)[1]}
        q = add(q,t)
        r = sub(r,mul(t,den))
    return q,r

def gcd(a,b):
    if lterm(b)[0] > lterm(a)[0]:
        a,b = b,a
    while len(b) != 0:
        r = ldiv(a,b)[1]
        a = b
        b = r
        #print(a)
        #print(b)
        #input('fdfs')
    return a

def gcdtprs(a,b):
    if lterm(b)[0] > lterm(a)[0]:
        a,b = b,a
    alpha = 1
    while len(b) != 0:
        r = ldiv(scalmul(lterm(b)[1]**(lterm(a)[0]-lterm(b)[0]+1),a),b)[1]
        r = scaldiv(r,alpha)
        a,b = b,r
    return a

def gcdpprs(a,b):
    from fractions import gcd
    from functools import reduce
    if lterm(b)[0] > lterm(a)[0]:
        a,b = b,a
    while len(b) != 0:
        r = ldiv(scalmul(lterm(b)[1]**(lterm(a)[0]-lterm(b)[0]+1),a),b)[1]
        #print(r)
        alpha = reduce(lambda x,y: gcd(x,y),[r[_] for _ in r],0)
        #print(alpha)
        r = scaldiv(r,alpha)
        a,b = b,r
    return a

def gcdsspr(a,b):
    from fractions import Fraction as F
    if lterm(b)[0] > lterm(a)[0]:
        a,b = b,a
    a,b = dict(a),dict(b)
    h = F(1)
    while len(b) != 0:
        delta = lterm(a)[0] - lterm(b)[0]
        beta = (-1)**(delta+1)*lterm(a)[1]*h**delta
        h = h * (lterm(b)[1]/h)**delta
        a,b = b,scaldiv(ldiv(scalmul(lterm(b)[1]**(delta+1),a),b)[1],beta)
    return a