#15820: Implement sequences of bounded integers
-------------------------------------+-------------------------------------
Reporter: SimonKing | Owner:
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.4
Component: algebra | Resolution:
Keywords: sequence bounded | Merged in:
integer | Reviewers: Simon King
Authors: Simon King, | Work issues:
Jeroen Demeyer | Commit:
Report Upstream: N/A | 6e03f19d4bc2379e44e0b8adc32c13ac6e0bcabb
Branch: | Stopgaps:
u/SimonKing/ticket/15820 |
Dependencies: #17195, #17196 |
-------------------------------------+-------------------------------------
Comment (by SimonKing):
I have implemented `mpn_equal_bits_shifted`. I do ''not'' use `mpn_rshift`
followed be `mpn_cmp`, since this would mean to touch each limb twice
(once
for shifting, once for comparison), even if the difference occurs early in
the
sequence. Of course, using such function simplifies the code of
`biseq_contains` and `biseq_max_overlap` considerably.
Here I redo the containment tests from comment:157, giving timings with
the new
code and (in brackets) with the previous code (I would not directly
compare
with comment:157, since the previous code differs too much from the code
back
at comment:157).
{{{
sage: from sage.data_structures.bounded_integer_sequences import
BoundedIntegerSequence
sage: L0 = [randint(0,7) for i in range(5)]
sage: L1 = [randint(0,15) for i in range(15)]
sage: L2 = [randint(0,31) for i in range(50)]
sage: L3 = [randint(0,31) for i in range(5000)]
sage: T0 = tuple(L0); T1 = tuple(L1); T2 = tuple(L2); T3 = tuple(L3)
sage: S0 = BoundedIntegerSequence(8, L0)
sage: S1 = BoundedIntegerSequence(16, L1)
sage: S2 = BoundedIntegerSequence(32, L2)
sage: S3 = BoundedIntegerSequence(32, L3)
sage: L0x = [randint(0,7) for i in range(5)]
sage: L1x = [randint(0,15) for i in range(15)]
sage: L2x = [randint(0,31) for i in range(50)]
sage: L3x = [randint(0,31) for i in range(5000)] # verified that they
differ from L0,L1,L2,L3
sage: S0x = BoundedIntegerSequence(8, L0x)
sage: S1x = BoundedIntegerSequence(16, L1x)
sage: S2x = BoundedIntegerSequence(32, L2x)
sage: S3x = BoundedIntegerSequence(32, L3x)
sage: S1y = BoundedIntegerSequence(16, L1)
sage: S2y = BoundedIntegerSequence(32, L2)
sage: S3y = BoundedIntegerSequence(32, L3)
sage: S0z1 = S0+S0
sage: S0z2 = S0+S0x
sage: S1z1 = S1+S1
sage: S1z2 = S1+S1x
sage: S2z1 = S2+S2
sage: S2z2 = S2+S2x
sage: S3z1 = S3+S3
sage: S3z2 = S3+S3x
sage: timeit("S0x in S0z2", number=1000000)
1000000 loops, best of 3: 190 ns per loop (384 ns per loop)
sage: timeit("S1x in S1z2", number=1000000)
1000000 loops, best of 3: 282 ns per loop (519 ns per loop)
sage: timeit("S2x in S2z2", number=1000000)
1000000 loops, best of 3: 644 ns per loop (2.1 µs per loop)
sage: timeit("S3x in S3z2", number=1000)
1000 loops, best of 3: 50.2 µs per loop (2.36 ms per loop)
}}}
So, there is a very clear improvement, and this time it concerns a
function
that I use very extensively in my applications.
Jeroen, I think that with the new commit I addressed all of your concerns,
hence, for now I will move on to the follow-up tickets (i.e., cythoned
quiver
paths and the non-commutative F5 algorithm that is not on trac yet).
--
Ticket URL: <http://trac.sagemath.org/ticket/15820#comment:302>
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.
