#16308: Improve sums of squares
-------------------------------------+-------------------------------------
Reporter: jdemeyer | Owner:
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.3
Component: number theory | Resolution:
Keywords: | Merged in:
Authors: Jeroen Demeyer, | Reviewers:
Vincent Delecroix | Work issues:
Report Upstream: N/A | Commit:
Branch: | 9b81872a5ff12ba45acbbc32a711c85f2fd58d08
u/vdelecroix/16308 | Stopgaps:
Dependencies: |
-------------------------------------+-------------------------------------
Changes (by {'newvalue': u'Jeroen Demeyer, Vincent Delecroix', 'oldvalue':
u'Jeroen Demeyer'}):
* commit: 6b94a6576031e6e341143a4fc1fd83263a800ed9 =>
9b81872a5ff12ba45acbbc32a711c85f2fd58d08
* branch: u/jdemeyer/ticket/16308 => u/vdelecroix/16308
* author: Jeroen Demeyer => Jeroen Demeyer, Vincent Delecroix
Comment:
Hello,
I implemented what I said in Cython (i.e. `two_squares_pyx`,
`three_squares_pyx` and `four_squares_pyx`). Timings are now much better
for small values (but it also influences small values).
Based on the timings below (with the old version), I put the threshold to
500 for the three functions. But if you have strong opinion for another
threshold please tell me.
There are many comments, but is there somebody up for a review ?
Vincent
Two squares
{{{
sage: %timeit two_squares(101)
10000 loops, best of 3: 94.5 µs per loop
sage: %timeit two_squares_pyx(101)
1000000 loops, best of 3: 780 ns per loop
sage: timeit("try:\n two_squares(102)\nexcept ValueError:\n pass")
625 loops, best of 3: 57.4 µs per loop
sage: timeit("try:\n two_squares_pyx(102)\nexcept ValueError:\n
pass")
625 loops, best of 3: 6.4 µs per loop
sage: %timeit two_squares(200)
10000 loops, best of 3: 87.3 µs per loop
sage: %timeit two_squares_pyx(200)
1000000 loops, best of 3: 788 ns per loop
sage: timeit("try:\n two_squares(201)\nexcept ValueError:\n pass")
625 loops, best of 3: 39.6 µs per loop
sage: timeit("try:\n two_squares_pyx(201)\nexcept ValueError:\n
pass")
625 loops, best of 3: 6.61 µs per loop
sage: %timeit two_squares(305)
10000 loops, best of 3: 158 µs per loop
sage: %timeit two_squares_pyx(305)
1000000 loops, best of 3: 998 ns per loop
sage: timeit("try:\n two_squares(304)\nexcept ValueError:\n pass")
625 loops, best of 3: 50.8 µs per loop
sage: timeit("try:\n two_squares_pyx(304)\nexcept ValueError:\n
pass")
625 loops, best of 3: 6.71 µs per loop
sage: %timeit two_squares(400)
10000 loops, best of 3: 69.4 µs per loop
sage: %timeit two_squares_pyx(400)
1000000 loops, best of 3: 1.01 µs per loop
sage: timeit("try:\n two_squares(402)\nexcept ValueError:\n pass")
625 loops, best of 3: 57.5 µs per loop
sage: timeit("try:\n two_squares_pyx(402)\nexcept ValueError:\n
pass")
625 loops, best of 3: 6.85 µs per loop
sage: %timeit two_squares(500)
10000 loops, best of 3: 119 µs per loop
sage: %timeit two_squares_pyx(500)
1000000 loops, best of 3: 1.18 µs per loop
sage: timeit("try:\n two_squares(501)\nexcept ValueError:\n pass")
625 loops, best of 3: 39.5 µs per loop
sage: timeit("try:\n two_squares_pyx(501)\nexcept ValueError:\n
pass")
625 loops, best of 3: 6.76 µs per loop
}}}
Three squares
{{{
sage: %timeit three_squares(106)
1000 loops, best of 3: 266 µs per loop
sage: %timeit three_squares_pyx(106)
1000000 loops, best of 3: 1.38 µs per loop
sage: timeit("try:\n three_squares(103)\nexcept ValueError:\n pass")
625 loops, best of 3: 52.2 µs per loop
sage: timeit("try:\n three_squares_pyx(103)\nexcept ValueError:\n
pass")
625 loops, best of 3: 6.9 µs per loop
sage: %timeit three_squares(200)
1000 loops, best of 3: 205 µs per loop
sage: %timeit three_squares_pyx(200)
1000000 loops, best of 3: 1.81 µs per loop
sage: timeit("try:\n three_squares(303)\nexcept ValueError:\n pass")
625 loops, best of 3: 52.1 µs per loop
sage: timeit("try:\n three_squares_pyx(303)\nexcept ValueError:\n
pass")
625 loops, best of 3: 9.24 µs per loop
sage: %timeit three_squares(406)
1000 loops, best of 3: 189 µs per loop
sage: %timeit three_squares_pyx(406)
100000 loops, best of 3: 3.46 µs per loop
sage: timeit("try:\n three_squares(407)\nexcept ValueError:\n pass")
625 loops, best of 3: 51.6 µs per loop
sage: timeit("try:\n three_squares_pyx(407)\nexcept ValueError:\n
pass")
625 loops, best of 3: 10.5 µs per loop
sage: %timeit three_squares(500)
10000 loops, best of 3: 167 µs per loop
sage: %timeit three_squares_pyx(500)
100000 loops, best of 3: 3.89 µs per loop
sage: timeit("try:\n three_squares(503)\nexcept ValueError:\n pass")
625 loops, best of 3: 51.2 µs per loop
sage: timeit("try:\n three_squares_pyx(503)\nexcept ValueError:\n
pass")
625 loops, best of 3: 10.7 µs per loop
}}}
Four squares
{{{
sage: %timeit four_squares(503)
1000 loops, best of 3: 259 µs per loop
sage: %timeit four_squares_pyx(503)
100000 loops, best of 3: 13.5 µs per loop
}}}
----
New commits:
||[http://git.sagemath.org/sage.git/commit/?id=616c606cf62a0f74a3f36a9cf86d6322c43c2d77
616c606]||{{{trac #16308: cython version of x_squares}}}||
||[http://git.sagemath.org/sage.git/commit/?id=9b81872a5ff12ba45acbbc32a711c85f2fd58d08
9b81872]||{{{trac #16308: add the file arith_pyx.pyx}}}||
--
Ticket URL: <http://trac.sagemath.org/ticket/16308#comment:31>
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.
