#15820: Implement sequences of bounded integers
--------------------------------------------+------------------------
Reporter: SimonKing | Owner:
Type: enhancement | Status: new
Priority: major | Milestone: sage-6.3
Component: algebra | Resolution:
Keywords: sequence bounded integer | Merged in:
Authors: | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
Dependencies: | Stopgaps:
--------------------------------------------+------------------------
Comment (by SimonKing):
I did a lot of benchmark tests for the different implementations (using
`long*` or `char*` or `mpz_t` to store sequences of bounded integers,
using cdef functions that operate on fused types) and eventually found
that using GMP (i.e., `mpz_t`) is fastest in ''all'' tests, by a wide
margin.
Why did I not find this result before? Well, part of the reason is that
GMP sometimes provides different functions to do the same job, and in the
past few days I considerably improved my usage of the various
possibilities. For example, `mpz_t` can be initialised in different ways.
If one uses `mpz_init`, then the assignment that will follow results in a
re-allocation. Since the length of the concatenation of two tuples is
known in advance, this resulted in a speed-up of concatenation, actually
it became twice as fast.
And this result is not surprising. After all, GMP has to implement the
same bitshift and comparison operations for bit arrays that I was
implementing in the "`long*`" approach, too. But GMP probably uses
implementation techniques that I can not even dream of.
Now, my plan is to
- create some `ctypedef struct bounded_int_tuple` that is based on `mpz_t`
and is the underlying C structure for tuples of bounded integers
- provide a collection of cdef (inline) functions, operating on
`bounded_int_tuple`, for concatenation, copying, comparison and so on
- wrap it in a cdef class `BoundedIntegerTuple`. This will probably
''not'' derive from `Element`: I think it makes no difference from the
point of view of memory efficiency whether each `BoundedIntegerTuple`
stores a pointer to the parent of "all tuples of integers bounded by `B`"
or directly stores `B` as an unsigned int.
In a subsequent ticket, I plan to use it for quiver paths, and if the
combinat crowd cares, they can use it to make parts of sage.combinat.words
a lot faster.
Comments? Requests? Suggestion of alternatives?
--
Ticket URL: <http://trac.sagemath.org/ticket/15820#comment:47>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" 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 http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
