#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:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/jdemeyer/ticket/16308 | 6b94a6576031e6e341143a4fc1fd83263a800ed9
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by vdelecroix):
Hi there,
For very small integers (<500) a naive cython implementation is '''much'''
faster (at least x100)... as this was the initial purpose of Nathann I
make the remark here.
{{{
def two_squares_pyx(int n):
cdef int i,ii,j,nn
if n < 2:
return True
i = ii = 0
while ii < n:
j = 0
while j <= i:
nn = ii + j*j
if nn >= n:
break
j += 1
if nn == n:
return (i,j)
i += 1
ii = i*i
raise ValueError("%d is not the sum of 2 squares"%n)
}}}
then
{{{
sage: %timeit two_squares(37)
10000 loops, best of 3: 108 µs per loop
sage: %timeit two_squares_pyx(37)
1000000 loops, best of 3: 464 ns per loop
sage: %timeit two_squares(97)
10000 loops, best of 3: 185 µs per loop
sage: %timeit two_squares_pyx(97)
1000000 loops, best of 3: 558 ns per loop
sage: %timeit two_squares(212)
10000 loops, best of 3: 130 µs per loop
sage: %timeit two_squares_pyx(212)
1000000 loops, best of 3: 734 ns per loop
sage: %timeit two_squares(500)
10000 loops, best of 3: 131 µs per loop
sage: %timeit two_squares_pyx(500)
1000000 loops, best of 3: 1 µs per loop
}}}
What do you think of using it for entries < 500?
Vincent
--
Ticket URL: <http://trac.sagemath.org/ticket/16308#comment:25>
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.
