#15820: Implement sequences of bounded integers
--------------------------------------------+------------------------
Reporter: SimonKing | Owner:
Type: enhancement | Status: new
Priority: major | Milestone: sage-6.2
Component: algebra | Resolution:
Keywords: sequence bounded integer | Merged in:
Authors: | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
Dependencies: | Stopgaps:
--------------------------------------------+------------------------
Comment (by ncohen):
Yooooooo !!!
> No. We have
> {{{
> #!c
> cdef Integer NumberArrows
> cdef Integer IntegerMask
> cdef size_t ArrowBitSize, BigArrowBitSize
> cdef block* bitmask = NULL
> cdef block DataMask, BitMask
> cdef size_t ArrowsPerBlock, BigArrowsPerBlock
> cdef size_t ModBAPB, DivBAPB, TimesBABS, TimesBlockSize
> }}}
Hmmmm.. Can't they all be deduced from the type of implementation
(compressed long, for instance) and the number of bits per entry then ?
>
> For example, `ModBAPB` is used to replace `n%BigArrowsPerBlock` by a
bit-wise `and`, which is noticeably faster.
Yepyep of course.
> > If it is, did you decided whether you want to allow it to be
arbitrary, or if you want it to be a power of 2 ?
>
> Depending on the implementation...
Okay....
> > If it is a power of 2, then perhaps templates are sufficient, i.e.
"one data structure per value of this parameter". There are not so many
powers of 2 between 1 and 64 that make sense to store something `:-)`
>
> Isn't duplication of code supposed to smell?
Well, if it is a template the code is only implemented once. And it will
generate several data structures at compile time indeed, but each of them
will have a hardcoded constant, and you only implement one.
> Do I understand correctly: You suggest that we should ''not'' provide a
class `BoundedIntegerSequence` that can be used interactively in Sage, but
you suggest that we should just provide a couple of functions that operate
on C structures (say, `mpz_t` or `usigned long*`) and can only be used in
Cython code?
That's what I had in mind, but you make decisions here, pick what you
like.
It's a bit how bitsets are implemented. A C data structure, and an object
wrapper on top of it. Or C Graphs, with a data structure on top of it. It
is how Permutations should be implemented, too `:-P`
Well, you have a C object that you use when you want performance, and when
you don't care you use the higher-level implementations.
> Then it would be better to revert this ticket to its original purpose:
There would be...
> 1. ... cdef functions operating on `mpz_t` resp. on `unsigned long*`,
> 2. ... a Cython class `Path` using `mpz_t` resp. `unsigned long*` as a
cdef attribute, using the afore mentioned functions to implement
concatenation and iteration,
> 3. ... a subsequent ticket, implementing an F5 style algorithm to
compute standard bases, operating not with `Path` but with `mpz_t*` resp
`unsigned long**` (which will be the case anyway).
Well, I like this plan. What do you think ? Does it displease you in any
way ?
> No problem. I just want to know if people see the need to have a Cython
implementation of sequences of bounded integers, for use in Python.
I do not see how I could use it in my code at the moment, but I like the
idea of having such a data structure somewhere, ready to be used. Most
importantly, if you want speed, I think that having it available at two
different levels is a safe bet. You write more code, but you will know how
computations are spent in your time-critical functions.
Nathann
--
Ticket URL: <http://trac.sagemath.org/ticket/15820#comment:30>
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.
