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/5d92d02e-bba6-24df-c569-1d640ffbf59d%40gmail.com.
