import sympy as s
import numpy as np
import itertools
import math


def integerapproxoriginangles(denom,radius,number):
    """
    this computes a list containing integer approxmiations
    of the arguments times the number variable
    """
    result=[]
    for j in range(1, math.floor((denom)/2)):
        result.append(round(floor(2*number*N(arg(1+N(radius)*exp(2*I*pi*j/denom))))/2)) #the nested floor is to deal with sage not having round for algebraics
    return result


def makelattice(denom,radius,number):
    #compute the integer approximations of our angles using LLL
    values=integerapproxoriginangles(denom,radius,number)
    n=len(values)
    #make a list of vectors with the angles in the last row and with identifiers in the rest
    result=[]
    for i in range(n):
        a=np.zeros(n+1).astype('int64') #it is of length n+1 as there are n identifiers and one for value
        a[i]=1
        a[-1]=values[i]
        result.append(a)
    return result


def makelatticeincludepi(denom,radius,number):
    #compute the integer approximations of our angles including pi in the mix using LLL
    values=integerapproxoriginangles(denom,radius,number)
    n=len(values)
    result=[]
    #make a list of vectors with the angles in the last row and with identifiers in the rest
    for i in range(n):
        a=np.zeros(n+2).astype('int64')
        a[i]=1
        a[-1]=values[i]
        result.append(a)
    #add pi to the result list
    a=np.zeros(n+2).astype('int64') #it is length n+2 as there are n+1 identifiers and 1 value.
    a[n]=1
    a[-1]=round(number*pi)
    result.append(a)
    return result


def verify_candidate(denom,radius,candidate):
    """
    This function takes a candidate on LLL-form and checks if the formula is valid, see
    """
    temp=1
    temp2=1
    for j in range(len(candidate)-1):
        var=candidate[j]
        while var!=0:
            if var>0:
                temp *=1+QQbar(exp( I*pi*2*(j+1)/denom))*radius
                temp2*=1+QQbar(exp(-I*pi*2*(j+1)/denom))*radius
                var-=1
            if var<0:
                temp *=1+QQbar(exp(-I*pi*2*(j+1)/denom))*radius
                temp2*=1+QQbar(exp( I*pi*2*(j+1)/denom))*radius
                var+=1
    res=QQbar(temp-temp2)
    res.exactify()
    return bool(res==0)

def zero_formulas_lll(denom,radius,number=10**10):
    """
    This finds candidates using LLL and tries to verify them, outputting the list of proven formulas
    """
    lll=Matrix(makelattice(denom,radius,number)).LLL()
    result=[]
    for candidate in lll:
        if verify_candidate(denom,radius,candidate):
            result.append(candidate)
    return result

def pi_formulas_lll(denom,radius,number=10**10):
    """
    This finds candidates using LLL and tries to verify them, outputting the list of proven formulas
    """
    lll=Matrix(makelatticeincludepi(denom,radius,number)).LLL()
    result=[]
    for candidate in lll:
        if verify_candidate(denom,radius,candidate):
            result.append(candidate)
    return result

def test_if_candidate_is_in_space(candidate, radius, denom):
    """
    This takes a BBP form candidate and checks if it is in the subspace spanned by
    the vectors for the BBP form our main theorem gives for the
    arguements of 1+radius*exp(2pi*a/denom) for all integers a
    """
    V=VectorSpace(AA,denom)
    vectors=[]
    for i in range(1,denom//2):
        vec=[radius**j * (-1)**(j+1)*sin(j*i*2*pi/denom) for j in range(1,denom+1)]
        vectors.append(V(vec))
    S=V.subspace(vectors)
    n=len(S.basis())
    Sprime=V.subspace(vectors+[V(candidate)])
    m=len(Sprime.basis())
    return m==n

def find_relation_for_candidate_in_space(candidate, radius, denom):
    """
    This takes a BBP form candidate assumes it is in the space spanned by the bbp form
    of the arguements of 1+radius*exp(2pi*a/denom) given by main theorem
    It solves for the coefficients
    """
    V=VectorSpace(AA,denom)
    vectors=[]
    for i in range(1,denom//2):
        vec=[radius**j * (-1)**(j+1)*sin(j*i*2*pi/denom) for j in range(1,denom+1)]
        vectors.append(V(vec))
    return Matrix(vectors).solve_left(V(candidate))

def test_if_candidate_list_is_in_space(list_of_candidates, radius, denom):
    """
    This takes a list BBP form candidate and checks if any linear combination of them
    is in the subspace spanned by
    the vectors for the BBP form our main theorem gives for the
    arguements of 1+radius*exp(2pi*a/denom) for all integers a
    """
    V=VectorSpace(AA,denom)
    vectors=[]
    for i in range(1,denom//2):
        vec=[radius**j * (-1)**(j+1)*sin(j*i*2*pi/denom) for j in range(1,denom+1)]
        vectors.append(V(vec))
    S=V.subspace(vectors)
    n=len(S.basis())
    G=list(map(V,list_of_candidates))
    SG=V.subspace(G)
    k=len(SG.basis())
    Sprime=V.subspace(vectors+G)
    m=len(Sprime.basis())
    return (n,k,m)

def bbp_form_from_lll(lllform,radius,denom):
    result=[]
    for k in range(1,denom+1):
        val=0
        for j, count in enumerate(lllform):
            val+=count*radius**k*(-1)**(k+1)*sin(2*pi*k*(j+1)/denom)
        result.append(val)
    return result