I am just reading a text about Maple internals. They say that
on all "major" systems tested operations like sequential
creation of list, polynomial or a set is quadratic.
I mentioned previously that creating list adding elements
at the end is quadratic, but adding elemet to the front
(prepending) is linear. This has consequences for
polynomial arithmetic:
fn(n) == (sum := 0$POLY(INT); for i in 1..n repeat sum := i*x^i + sum; sum)
(28) -> f1000 := fn(1000);
Type: Polynomial(Integer)
Time: 0.00 (EV) + 0.00 (OT) = 0.01 sec
(29) -> f10000 := fn(10000);
Type: Polynomial(Integer)
Time: 0.06 (EV) = 0.06 sec
(30) -> f100000 := fn(100000);
Type: Polynomial(Integer)
Time: 0.52 (EV) = 0.52 sec
and timings scale linearly to larger values. Note that the
fastest (on this operation) major competitior, that is
Mathematica 9 needs 0.216s for 8000 terms and 0.946 for
16000. Magma 2.19, Maple 17 and Singular 3.1 need more
time (running on a faster machine).
A little extra comment: I gave explicit type to 0. Otherwise
interpreter will initally think that 'sum' is an Integer and
later notice that type changed. This disables compilation
so that function is much slower (but still linear) due to
interpretation.
Extra comment: This depends on the fact that polynomials
are stored as list, starting from term of highest degree.
Adding terms in wrong order would be quadratic, just
like other system. Sets use FlexibleArray as representation
and AFAICS expanding set element by element is quadratic
for any order of operations.
--
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 [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/fricas-devel.
For more options, visit https://groups.google.com/d/optout.
