search

JuliaAlgebra / DynamicPolynomials.jl

Multivariate polynomials implementation of commutative and non-commutative variables
Other
58 stars 20 forks source link

`gcd` throws LoadError: DivideError: integer division error #156

Open martinkjlarsson opened 3 months ago

martinkjlarsson commented 3 months ago

I work with some massive polynomials (close to 4000 terms) and when calling gcd I get the following error

ERROR: LoadError: DivideError: integer division error
Stacktrace:
  [1] div
    @ ./int.jl:295 [inlined]
  [2] div_multiple
    @ ~/.julia/packages/MultivariatePolynomials/TpRhf/src/division.jl:57 [inlined]
  [3] div_multiple
    @ ~/.julia/packages/MultivariatePolynomials/TpRhf/src/division.jl:59 [inlined]
  [4] div_multiple (repeats 2 times)
    @ ~/.julia/packages/MultivariatePolynomials/TpRhf/src/division.jl:85 [inlined]
  [5] div_multiple(f::Polynomial{DynamicPolynomials.Commutative{DynamicPolynomials.CreationOrder}, Graded{LexOrder}, Int64}, g::Polynomial{DynamicPolynomials.Commutative{DynamicPolynomials.CreationOrder}, Graded{LexOrder}, Int64}, mf::MutableArithmetics.IsMutable)
    @ MultivariatePolynomials ~/.julia/packages/MultivariatePolynomials/TpRhf/src/division.jl:140
  [6] #104
    @ ~/.julia/packages/MultivariatePolynomials/TpRhf/src/division.jl:99 [inlined]
  [7] map!(f::MultivariatePolynomials.var"#104#105"{Polynomial{DynamicPolynomials.Commutative{DynamicPolynomials.CreationOrder}, Graded{LexOrder}, Int64}, MutableArithmetics.IsMutable}, dest::Vector{Polynomial{DynamicPolynomials.Commutative{DynamicPolynomials.CreationOrder}, Graded{LexOrder}, Int64}}, A::Vector{Polynomial{DynamicPolynomials.Commutative{DynamicPolynomials.CreationOrder}, Graded{LexOrder}, Int64}})
    @ Base ./abstractarray.jl:3278
  [8] map_coefficients!(f::Function, p::Polynomial{DynamicPolynomials.Commutative{DynamicPolynomials.CreationOrder}, Graded{LexOrder}, Polynomial{DynamicPolynomials.Commutative{DynamicPolynomials.CreationOrder}, Graded{LexOrder}, Int64}}; nonzero::Bool)
    @ DynamicPolynomials ~/.julia/packages/DynamicPolynomials/3CVI5/src/poly.jl:362
  [9] map_coefficients!
    @ ~/.julia/packages/DynamicPolynomials/3CVI5/src/poly.jl:361 [inlined]
 [10] #map_coefficients#14
    @ ~/.julia/packages/MultivariatePolynomials/TpRhf/src/polynomial.jl:613 [inlined]
...

The stack trace continues for quite a while. This does not happen with TypedPolynomials.jl, so it may be a bug with DynamicPolynomials.jl. Maybe this is a bit unusual use case, but I figured I'd submit an issue.

A minimal working example is attached as a text file as the polynomials are huge. error.txt

Version info: DynamicPolynomials v0.5.5 TypedPolynomials v0.4.1 Julia Version 1.10.2

sumiya11 commented 3 months ago

I was just passing by (incidentally looking at existing gcd issues), I think the problem here might be integer overflow https://github.com/JuliaAlgebra/DynamicPolynomials.jl/issues/107.

Changing the lines in your file

p1 = sum(c1 .* vec(prod(v1 .^ e1, dims=1)))
p2 = sum(c2 .* vec(prod(v2 .^ e2, dims=1)))

to

p1 = sum(BigInt.(c1) .* vec(prod(v1 .^ e1, dims=1)))
p2 = sum(BigInt.(c2) .* vec(prod(v2 .^ e2, dims=1)))

seems to work for me.

martinkjlarsson commented 3 months ago

Ahh, makes sense I suppose. Thanks!

blegat commented 3 months ago

Yes, we don't automatically promote to BigInt, we might want to use checked operations