Hi all,
I have this test code:

``````import Base.+

mutable struct Polynomial
data::Dict{Int, Real}

function Polynomial(data::Dict{Int, <:Real})
@assert all(n->n>=0, keys(data))
@assert all(!iszero, values(data))
new(data)
end
Polynomial() = new(Dict())
end

function +(P::Polynomial, Q::Polynomial)
""" P + Q """
R = Polynomial()
pds = keys(P.data)
qds = keys(Q.data)

for n in setdiff(pds, qds)
R.data[n] = P.data[n]
end

for n in setdiff(qds, pds)
R.data[n] = Q.data[n]
end

for n in pds ∩ qds
if (c = P.data[n] + Q.data[n]) != 0
R.data[n] = c
end
end
R
end

function +=(P::Polynomial, Q::Polynomial)
""" P += Q """
pds = keys(P.data)
qds = keys(Q.data)

for n in setdiff(qds, pds)
P.data[n] = Q.data[n]
end

for n in pds ∩ qds
if (c = P.data[n] + Q.data[n]) != 0
P.data[n] = c
end
end
end
``````

``````ERROR: LoadError: syntax: invalid identifier name "+="
Stacktrace:
 include at .\boot.jl:317 [inlined]
 include(::Module, ::String) at .\sysimg.jl:29
 exec_options(::Base.JLOptions) at .\client.jl:231
 _start() at .\client.jl:425
in expression starting at C:\Users\User\Desktop\Tfach\julia_project\test.jl:36
``````

how can I define the += operator ?

See this section of the manual, specifically writing `x += 3` is equivalent to writing `x = x + 3`. In other words, you’d just overload `+`.

2 Likes

See also https://github.com/JuliaLang/julia/issues/3217 and https://github.com/JuliaLang/julia/issues/249 for why we opted not to allow `+=` etcetera to be overloadable separately from `+`, unlike Python.

(For defining in-place operations, `.+=` is much more powerful because it fuses with other “dot” operations, and `.+=` can be customized via the broadcast machinery.)

4 Likes

I don’t think `.+=` is suitable because here (and eventually in many other cases) the type is not a container (although might be seen as one), the required operation is on the type itself, not its elements.
just a quick benchmark shows a speed and space gain between the two versions (Note: renamed `+=` => `iadd`):

``````julia> using BenchmarkTools

julia> P = Polynomial(Dict(1=>2, 2=>-5))
Polynomial(Dict{Int64,Real}(2=>-5,1=>2))

julia> Q = Polynomial(Dict(0=>5, 1=>-2, 3=>5))
Polynomial(Dict{Int64,Real}(0=>5,3=>5,1=>-2))

julia> @btime \$P = \$P + \$Q
2.941 μs (27 allocations: 2.70 KiB)
Polynomial(Dict{Int64,Real}(0=>5,2=>-5,3=>5))

1.829 μs (17 allocations: 1.08 KiB)
``````
1 Like

Incidentally, perhaps you should make it `Dict{Int, T}` and `T` a type parameter, for performance. See Performance Tips · The Julia Language

1 Like

yes but the Polynomial takes an arbitrary `Real`.
changing the type to be more specific

``````mutable struct Polynomial{T<:Real}
data::Dict{Int, T}

function Polynomial(data::Dict{Int, <:Real})
@assert all(n->n>=0, keys(data))
@assert all(!iszero, values(data))
new(data)
end
Polynomial() = new(Dict())
end
``````

produces this error:

``````ERROR: LoadError: syntax: too few type parameters specified in "new{...}"
Stacktrace:
 include at .\boot.jl:317 [inlined]
 include(::Module, ::String) at .\sysimg.jl:29
 exec_options(::Base.JLOptions) at .\client.jl:231
 _start() at .\client.jl:425
in expression starting at C:\Users\User\Desktop\Tfach\julia_project\test.jl:5
``````

why is that ?

Excuse me for asking, but isn’t implementing polynomials using Dicts incredibly inefficient? It also seems to lead to very messy code. Why not use tuples or StaticArrays to hold the coefficients? Or maybe just plain vectors would be the easiest.

I don’t know if it’s “incredibly” inneficient, but it’s just for academic purpose, I have a python exercice to implement polynomials using dicts and i wanted to reimplement it as is in julia.

Because your type is parametric and `new` needs that information:

``````mutable struct Polynomial{T <: Real}
data::Dict{Int, T}

function Polynomial(data::Dict{Int, W}) where {W <: Real}
@assert all(n->n>=0, keys(data))
@assert all(!iszero, values(data))
new{W}(data)
end
Polynomial{T}() where {T <: Real} = new{T}(Dict{Int, T}())
# and for a default of `Real`
# Polynomial() = Polynomial{Real}()
end
``````

EDIT: Note that the type assertion `T <: Real` in the constructors is redundant - it’s already ensured by the type signature itself and technically doesn’t need to be checked in the constructor again.

1 Like

OK, that’s fine. It just seems so much more obvious to use vectors (or tuples) which have integer indices by default, than to use dicts. I guess it can be useful if you have very widely separated terms, like 2x^3 + 11x^{74} or something.

Python loves dicts, but in Julia they are not necessarily the obvious goto solution.

Thanks, I just found out that examining the code in Polynomials.jl

I guess dicts do have some advantage here in making sure the uniqueness of the degrees.

In that case, would a `SparseVector` be good as well? This would need some testing, but I’m feeling lucky today in saying it would be easier to use with existing multiplication etc.

The indices of the vector or tuple would be equivalent to the power at that position in the example by @DNF - for example, `v = [3 0 0 2 0]` would uniquely describe the polynomial 3x^4 + 2x.

Not quite sure what you mean.

A quick and dirty test using vectors gave me a 60x speedup using vectors and 10-15th power polynomials, both for construction and addition. If you have only small polynomials, you can probably get incredible speedups with tuples/staticvectors, though at the cost of more messing about with type parameters and maybe generated functions.