#15404: Change coprime_integers(n) in Integer class to use sieving instead of
naive
gcd
-----------------------------------+---------------------------------------
Reporter: spice | Owner: Simon Spicer
Type: enhancement | Status: needs_work
Priority: minor | Milestone: sage-5.13
Component: basic | Resolution:
arithmetic | Merged in:
Keywords: coprime, | Reviewers: William Stein, Hao Chen
integer | Work issues:
Authors: Simon Spicer | Commit:
Report Upstream: N/A | Stopgaps:
Branch: |
Dependencies: |
-----------------------------------+---------------------------------------
Comment (by spice):
New patch replaces previous patch. The method now uses naive gcd if both
self and m are < 1000, since this seems to be faster.
Some timings. Old code:
{{{
sage: %timeit 100.coprime_integers(100)
10000 loops, best of 3: 44.5 us per loop
sage: %timeit 101.coprime_integers(101)
10000 loops, best of 3: 52.6 us per loop
sage: %timeit 1000.coprime_integers(1000)
1000 loops, best of 3: 529 us per loop
sage: %timeit (10^6+12).coprime_integers(10^6+12)
1 loops, best of 3: 603 ms per loop
sage: %timeit (next_prime(10^6)).coprime_integers(10^6)
1 loops, best of 3: 795 ms per loop
sage: %timeit (10^8+512).coprime_integers(10^5)
10 loops, best of 3: 55.9 ms per loop
sage: %timeit (10^8+512).coprime_integers(10^7)
1 loops, best of 3: 5.61 s per loop
}}}
New code (without naive method for small inputs):
{{{
sage: %timeit 100.coprime_integers(100)
10000 loops, best of 3: 145 us per loop
sage: %timeit 101.coprime_integers(101)
10000 loops, best of 3: 139 us per loop
sage: %timeit 1000.coprime_integers(1000)
1000 loops, best of 3: 510 us per loop
sage: %timeit (10^6+12).coprime_integers(10^6+12)
1 loops, best of 3: 373 ms per loop
sage: %timeit (next_prime(10^6)).coprime_integers(10^6)
1 loops, best of 3: 383 ms per loop
sage: %timeit (10^8+512).coprime_integers(10^5)
10 loops, best of 3: 39.8 ms per loop
sage: %timeit (10^8+512).coprime_integers(10^7)
1 loops, best of 3: 3.98 s per loop
#MemoryError for m=10^8
}}}
The new code should be faster when self has few prime factors, but both
old and new code scale with m, the bound to which integers coprime to self
are returned, since we need to fit that many sage integers in memory.
--
Ticket URL: <http://trac.sagemath.org/ticket/15404#comment:5>
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/groups/opt_out.
