Hello, I’m getting the error given below continuosly. I know that there is a built-in function named “coeffs” in Julia and I want to use it. I’m trying to implement Zippel’s Algorithm. I also asked it on stackoverflow but couldn’t find a solution. Can you please help me? Thanks in advance.
stackoverflow link: python - I try using SymPy in Julia 1.7.1 and get "coeffs not found" error - Stack Overflow
Here is the error:
┌ Warning: `vendor()` is deprecated, use `BLAS.get_config()` and inspect the output instead
│ caller = npyinitialize() at numpy.jl:67
└ @ PyCall C:\Users\Ashraf\.julia\packages\PyCall\L0fLP\src\numpy.jl:67
ERROR: LoadError: KeyError: key :coeffs not found
Stacktrace:
Stacktrace:
[1] __getproperty(o::PyCall.PyObject, s::Symbol)
@ PyCall C:\Users\Ashraf\.julia\packages\PyCall\L0fLP\src\PyCall.jl:307
[2] getproperty
@ C:\Users\Ashraf\.julia\packages\PyCall\L0fLP\src\PyCall.jl:312 [inlined]
[3] getproperty
@ C:\Users\Ashraf\.julia\packages\SymPy\7xLLa\src\matrix.jl:52 [inlined]
[4] sparse_interpolation(x_var::Tuple{Sym, Sym, Sym}, a::Vector{Int64}, d::Int64)
@ Main D:\Desktop\Code\zippel.jl:175
[5] top-level scope
@ D:\Desktop\Code\zippel.jl:210
in expression starting at D:\Desktop\Code\zippel.jl:210
My Code:
using SymPy
using Random
using PyCall
using Polynomials
prime = 10 ^ 9 + 7
function pulverizer(a,b)
if a == 0
return 0,1
end
a = []
x,y = pulverizer(b%a, a)
a = push!(a,(x,y))
return y - (b/a) * x, x
end
function gcd(a,b)
if a == 0
return b
else
return gcd(b%a, a)
end
end
#=
dense interpolation algorithm 'D'.
Gives polynomial that fits all the given points.
Polynomial is such that, f(p_i) = m_i
=#
function dense_interpolation(p, m)
x = symbols("x")
f = m[1] * x ^ 0
# print(typeof(f))
q = x - p[1]
for i in 1:length(p)
temp = q.subs(x, p[i])
qpi_inv = q.subs(x, p[i]) ^ (-1)
f += qpi_inv * q * (m[i] - f.subs(x, p[i]))
q = (x - p[i]) * q
end
if f == NaN
return sympify(1)
else
return expand(f)
end
end
# ORACLE function 'F' which gives output of function at given points
function oracle(l)
l = [1,2,3]
x, y, z = symbols("x y z")
# func = 5*(x^4)*(y^2)*(z^3) + (x^3*y*z^2) + x + 8*y*z*x^2 + 3*x^5*y^5*z^5
func = (y^2*z^2 + y^2*z + 2*x^2*y*z + x*z)*y^2*z^2 + y^2*z + 2*x^2*y*z + x*z
func.subs(Dict("x"=>l[1], "y"=> l[2], "z"=> l[3]))
end
function oracle_gcd(l)
x, y, z = Symbol("x y z")
d = y^2*z^2 + y^2*z + 2*x^2*y*z + x*z
f = z^2 + y^2*z + x^2*y*z + x*z + x^2*y^2
g = y*z + 2*x*z + z + x
f1 = f*d
f2 = g*d
return gcd(f1.subs(Dict("x" => l[1], "y" => l[2], "z" => l[3])), f2.subs(Dict("x" => l[1], "y" => l[2], "z" => l[3])))
end
# sparse interpolation algorithm 'S'
function sparse_interpolation(x_var, a, d)
S = [sympify(1)]
p0 = sympify(oracle(a))
# print(p0, 'p0')
L = []
#iterate through each variable
for i in 1:length(x_var)
#print('i: ', i, '\n')
r = []
X = x_var[i]
P = []
#iterate 'd' times corresponding to number of degrees
for j in 1:d
#print('j = ', j, '\n')
#pick rj
temp = rand(1:10000)
# print('r_j', temp)
push!(r,temp)
#list for linear equations
L = []
t = length(S)
skeletal = sympify(0)
str = string(t+1)
str = string("g0:", str)
G = symbols(str)
# generate a skeletal polynomial from S
for k in 1:t
skeletal += G[k] * S[k]
end
# iterate 't' times where t is number of monomials in skeletal polynomial
for k in 1:t
#=
for i=1, there is no need to solve system of linear equations
we append the output of oracle [F] in the list 'P'
otherwise, we need to create a list 'L' of 't' linear equations
=#
if i == 1
oracle_out = oracle([r[j]] .+ a[1:length(a)])
push!(P, oracle_out)
sub_list = [(x_var[tem], a[tem]) for tem in 1:i]
push!(L,skeletal.subs(sub_list) - oracle_out)
else
A = [rand(1:10000) for r in 1:i]
or_lis = A + [r[j]] + a[i+1:length(a)]
oracle_out = oracle(or_lis)
sub_list = [(x_var[tem], A[tem]) for tem in 1:i]
push!(L,skeletal.subs(sub_list)-oracle_out)
end
end
#=
if i != 1, then solve the system of linear
equation and produce a polynomial pj
append the produced polynomial to the list P
=#
if i != 1
sol1 = linsolve(L,G)
next = iterate(sol1)
(val, state) = next
solution = PyAny(val)
#print("solution: ", length(solution[1].free_symbols))
temp_p = sympify(0)
for mon in 1:length(S)
temp_p = temp_p + S[mon]*solution[mon]
end
push!(P,temp_p)
end
end
#=
For i = 1, pass the list p directly to the dense_interpolation algorithm 'D'.
Store the coefficients to the list 'S' and the resulting polynomial in p0
If i is not 1, then for each monomial is 'S', pass the corresponding coefficients from
list 'P' and from p0 to the dense_interpolation algorithm 'D'.
Merge each monomial to its corresponding result from 'D' and simplify
=#
if i == 1
# print([p0] + P)
# print([p0] + P, "P\n", [a[1]] + r, 'r')
#p = []
#push!(p,P[1])
#println(size([a[1]]))
#println(a)
#println(r)
p0 = sympify(dense_interpolation([a[1]] .+ r, [p0] .+ P).subs(Symbol('x'), x_var[1]))
println(typeof(p0))
S = [p0].coeffs().keys()
# print("p0: ", expand(p0), '\n', 'S:', S, '\n')
# print("p0: ", p0, "\nS: ", S, '\n')
# print(p0.as_coefficients_dict(), " as coeff dict")
else
P = [p0] + P
r = [a[i]] + r
p0 = sympify(0)
# print(P, "P\n", r, 'r')
for mon in 1:length(S)
p_i_temp = []
# m_i_temp = []
for pol in 1:length(P)
p_i_temp += [P[pol].as_coefficients_dict()[S[mon]]]
end
# print(p_i_temp, "p_i_\n", "r\n")
interp_temp = dense_interpolation(r, p_i_temp).subs(Symbol('x'), x_var[i])
#print("interp_temp: ", interp_temp)
p0 += S[mon]*interp_temp
end
p0 = expand(p0)
S = p0.as_coefficients_dict().keys()
# print("p0: ", expand(p0), '\n', "s: ", s, '\n')
end
end
return p0
end
X = symbols("x0:3")
a = [1,2,3]
print(sparse_interpolation(X,a,4))