Dear all,
A mere two years after ticket #4000 was opened on trac and a little
work during Sage Days 24 in Linz, there is now a set of patches (ready
for review!) attached to the ticket that provides an implementation of
QQ[] via FLINT 1.
This note's main purpose is to let everyone know about this possible
improvement and to provide some advertisement in the form of a small
selection of performance comparisons. I am hoping this will generate
further interest in the ticket and accelerate the review process.
For the comparisons, I have chosen four operations: addition and
multiplication (basic arithmetic), greatest common divisor (used in
fraction fields, in particular), and element initialization from lists
(used in many places). The bottom line is that the "simple"
operations addition and initialization require a comparable amount of
time, whereas the operations multiplication and gcd are much faster in
the new implementation (using FLINT), even more so as the degrees of
the polynomials considered increase.
I'm looking forward to your comments and suggestions,
Sebastian
Addition
--------
sage: R.<t> = QQ[]
sage: f = R.random_element(10)
sage: g = R.random_element(10)
sage: timeit('f + g')
deg(f) 10 50 100 500 1000 4000
Old 18.1 µs 24.4 µs 32.7 µs 98.1 µs 186 µs 706 µs
New 4.56 µs 9.16 µs 22.4 µs 198 µs 377 µs 2.25 ms
Multiplication
--------------
sage: R.<t> = QQ[]
sage: f = R.random_element(10)
sage: g = R.random_element(10)
sage: timeit('f * g')
deg(f) 10 50 100 500 1000 4000
Old 101 µs 828 µs 2.99 ms 48.9 ms 177 ms 2.09 s
New 5.98 µs 26.5 µs 80.5 µs 1.78 ms 5.2 ms 48 ms
GCD
---
sage: R.<t> = QQ[]
sage: f = R.random_element(10)
sage: g = R.random_element(floor(f.degree() / sqrt(2)))
sage: timeit('f.gcd(g)')
deg(f) 10 50 100 500 1000 4000
Old 1.01 ms 1.78 s 36.5 s > 30 mins ?? ??
New 16.1 µs 54.8 µs 133 µs 5.92 ms 17.6 ms 373 ms
Initialization from list
------------------------
sage: R.<t> = QQ
sage: L = [QQ.random_element() for i in range(10)]
sage: timeit('R(L)')
len(f) 10 50 100 500 1000 4000
Old 71.4 µs 164 µs 276 µs 1.12 ms 2.16 ms 8.59 ms
New 20.5 µs 41.2 µs 64.3 µs 262 µs 520 µs 2.02 ms
--
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to
sage-devel+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org
