Instantly share code, notes, and snippets.

# benruijl/GCD benchmark.md

Last active June 28, 2024 09:30
Show Gist options
• 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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 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]
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 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)