Dnia Thu, Sep 14, 2023 at 09:02:38PM +0200, Valentin Hirschi napisał(a):
> Dear Fricas developers,
>
> I am playing around benchmarking CAS for the computation of polynomial GCDs
> with tests similar as those given in this paper:
> https://arxiv.org/pdf/2304.13418.pdf.
>
> More specifically I am using the following test using `Symbolica
> <https://symbolica.io/>` Python API:
>
> ```python
> a = Expression.parse('(1 + 3*x1 + 5*x2 + 7*x3 + 9*x4 + 11*x5 + 13*x6 +
> 15*x7)^7 - 1').to_rational_polynomial()
> b = Expression.parse('(1 - 3*x1 - 5*x2 - 7*x3 + 9*x4 - 11*x5 - 13*x6 +
> 15*x7)^7 + 1').to_rational_polynomial()
> g = Expression.parse('(1 + 3*x1 + 5*x2 + 7*x3 + 9*x4 + 11*x5 + 13*x6 -
> 15*x7)^7 + 3').to_rational_polynomial()
> ag = a * g
> bg = b * g
> print(g.gcd(bg) - g)
> ```
>
> Which runs in about 7 seconds on my laptop and prints out the expected 0.
>
> Then with `FriCAS`, I am doing:
> ```
>
> 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 := a * g;
>
> bg := b * g;
>
> gcd(ag, bg) -g
> ```
>
> which runs in about 25 seconds on my laptop but **does not evaluate to zero*
> *!
>
> My question is thus two-fold:
>
> a) Is this non-zero result expected? What is the proper way to get the
> correct GCD?
As Ralf wrote, gcd is not unique and FriCAS produces correct gcd, but
different to what you expect. In FriCAS appropriate test is:
(6) -> gg := gcd(ag, bg);
Type: Polynomial(Integer)
Time: 0 (IN) + 13.30 (EV) + 0.01 (OT) = 13.31 sec
(7) -> gg exquo g
(7) - 1
Type: Union(Polynomial(Integer),...)
Time: 0 (IN) + 0 (EV) + 0.00 (OT) = 0.00 sec
> b) Is my usage of `gcd` above the fastest way to compute polynomial GCDs
> and therefore a fair comparison with other CAS?
gcd command is supposed to use fastest method so this is fair. There
is one method to make things faster (if you did not do this already).
Namely, compile FriCAS yourself passing to configure additional
option '--enable-algebra-optimization="((speed 3) (safety 0))"'.
On fast machine using FriCAS build without this option gcd need
17.09s. Build with that option needs 13.31s.
--
Waldek Hebisch
--
You received this message because you are subscribed to the Google Groups
"FriCAS - computer algebra system" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to fricas-devel+unsubscr...@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/fricas-devel/ZQOJYEUt7%2BcDCPy0%40mail.math.uni.wroc.pl.
