Skip to content

Instantly share code, notes, and snippets.

@benruijl
Last active June 28, 2024 09:30
Show Gist options
  • Save benruijl/3c53b1b0aea88b978ae609e73693fdbc to your computer and use it in GitHub Desktop.
Save benruijl/3c53b1b0aea88b978ae609e73693fdbc to your computer and use it in GitHub Desktop.
A benchmark for polynomial GCDs
Tool Timing (s)
Symbolica 4.1
Mathematica 89
Sympy 3663
a = (1 + 3*x1 + 5*x2 + 7*x3 + 9*x4 + 11*x5 + 13*x6 + 15*x7)^7 - 1
b = (1 - 3*x1 - 5*x2 - 7*x3 + 9*x4 - 11*x5 - 13*x6 + 15*x7)^7 + 1
g = (1 + 3*x1 + 5*x2 + 7*x3 + 9*x4 + 11*x5 + 13*x6 - 15*x7)^7 + 3
ag = Expand[a g]
bg = Expand[b g]
PolynomialGCD[ag, bg] - Expand[g]
from symbolica import Expression as E
a = E.parse('(1 + 3*x1 + 5*x2 + 7*x3 + 9*x4 + 11*x5 + 13*x6 + 15*x7)^7 - 1').to_polynomial()
b = E.parse('(1 - 3*x1 - 5*x2 - 7*x3 + 9*x4 - 11*x5 - 13*x6 + 15*x7)^7 + 1').to_polynomial()
g = E.parse('(1 + 3*x1 + 5*x2 + 7*x3 + 9*x4 + 11*x5 + 13*x6 - 15*x7)^7 + 3').to_polynomial()
ag = a * g
bg = b * g
r = ag.gcd(bg) - g
from sympy.parsing.sympy_parser import parse_expr
from sympy import expand, gcd
a = parse_expr('(1 + 3*x1 + 5*x2 + 7*x3 + 9*x4 + 11*x5 + 13*x6 + 15*x7)**7 - 1')
b = parse_expr('(1 - 3*x1 - 5*x2 - 7*x3 + 9*x4 - 11*x5 - 13*x6 + 15*x7)**7 + 1')
g = parse_expr('(1 + 3*x1 + 5*x2 + 7*x3 + 9*x4 + 11*x5 + 13*x6 - 15*x7)**7 + 3')
ag = a * g
bg = b * g
r = gcd(ag, bg) - expand(g)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment