Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

gcd throws LoadError: DivideError: integer division error #156

Open
martinkjlarsson opened this issue Mar 20, 2024 · 3 comments
Open

gcd throws LoadError: DivideError: integer division error #156

martinkjlarsson opened this issue Mar 20, 2024 · 3 comments

Comments

@martinkjlarsson
Copy link

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
Copy link
Contributor

I was just passing by (incidentally looking at existing gcd issues), I think the problem here might be integer overflow #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
Copy link
Author

Ahh, makes sense I suppose. Thanks!

@blegat
Copy link
Member

blegat commented Mar 25, 2024

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

3 participants