Correction for the Maxima case: I used expression instead of polynomial in my previous version. The following version is corrected. (Using "rat" is the key.)
The conclusion also changes: the Maxima implementation is O(n^2) when polys are dense and O(n^3) when polys are sparse. Similar to current FriCAS. - Qian ==== n : 400; sparse : n; p : 0; q : 0; for i : 1 thru n do p : p + rat(x^i); for i : 1 thru n do q : q + rat(x^(i*sparse)); display2d : false; ttyoff : true; showtime : all; p * q; On 10/3/22 19:05, Qian Yun wrote:
Now some comparison with Maxima and Reduce: IIUC, Maxima implementation is "ptimes" at https://github.com/calyau/maxima/blob/master/src/rat3a.lisp#L850 And Reduce implementation is "poly!-multf" at https://github.com/reduce-algebra/reduce-algebra/blob/master/packages/poly/polrep.red#L199 The Maxima algorithm looks similar to ours, although it uses goto instead of loop. But it turns out it is O(n^3) complexity even for dense cases. The Reduce algorithm is recursive, basically p*q = p*car(q)+p*rest(q). So it's behavior is close to ours, but a bit more inefficient. Also it can stack overflow because it is recursive. Tests show it is (a little slower than) O(n^2) when polys are dense and it is O(n^3) when polys are sparse. - Qian Test files are: (Set "sparse" to 1 for dense cases and set it to "n" for sparse cases.) === Maxima === n : 400; sparse : n; p : 0; q : 0; for i : 1 thru n do p : p + x^i; for i : 1 thru n do q : q + x^(i*sparse); display2d : false; ttyoff : true; showtime : all; expand(p * q); ==== === Reduce === n:=400; sparse := n; p := 0; q := 0; for i := 1 step 1 until n do p := p + x^i; for i := 1 step 1 until n do q := q + x^(i*sparse); p*q; showtime; ====
-- 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 [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/fricas-devel/c1f37d5c-5cab-34aa-53a1-96e44a7fc10a%40gmail.com.
