Implement fast version of decomposition of (small) integers into sum of squares by direct method not relying on factorisation.
AUTHORS:
Return a 4-tuple of non-negative integers (i,j,k,l) such that and
.
The input must be lesser than , otherwise an
OverflowError is raised.
See also
four_squares() is much more suited for large input
EXAMPLES:
sage: from sage.rings.sum_of_squares import four_squares_pyx
sage: four_squares_pyx(15447)
(2, 5, 17, 123)
sage: 2^2 + 5^2 + 17^2 + 123^2
15447
sage: four_squares_pyx(523439)
(3, 5, 26, 723)
sage: 3^2 + 5^2 + 26^2 + 723^2
523439
sage: four_squares_pyx(2**32)
Traceback (most recent call last):
...
OverflowError: ...
TESTS:
sage: four_squares_pyx(0)
(0, 0, 0, 0)
sage: s = lambda (x,y,z,t): x**2 + y**2 + z**2 + t**2
sage: all(s(four_squares_pyx(n)) == n for n in xrange(5000,10000))
True
Return True if n is a sum of two squares and False otherwise.
The input must be smaller than , otherwise an
OverflowError is raised.
EXAMPLES:
sage: from sage.rings.sum_of_squares import is_sum_of_two_squares_pyx
sage: filter(is_sum_of_two_squares_pyx, range(30))
[0, 1, 2, 4, 5, 8, 9, 10, 13, 16, 17, 18, 20, 25, 26, 29]
sage: is_sum_of_two_squares_pyx(2**32)
Traceback (most recent call last):
...
OverflowError: ...
If n is a sum of three squares return a 3-tuple (i,j,k) of Sage integers
such that and
. Otherwise raise a ValueError.
The input must be lesser than , otherwise an
OverflowError is raised.
EXAMPLES:
sage: from sage.rings.sum_of_squares import three_squares_pyx
sage: three_squares_pyx(0)
(0, 0, 0)
sage: three_squares_pyx(1)
(0, 0, 1)
sage: three_squares_pyx(2)
(0, 1, 1)
sage: three_squares_pyx(3)
(1, 1, 1)
sage: three_squares_pyx(4)
(0, 0, 2)
sage: three_squares_pyx(5)
(0, 1, 2)
sage: three_squares_pyx(6)
(1, 1, 2)
sage: three_squares_pyx(7)
Traceback (most recent call last):
...
ValueError: 7 is not a sum of 3 squares
sage: three_squares_pyx(107)
(1, 5, 9)
sage: three_squares_pyx(2**32)
Traceback (most recent call last):
...
OverflowError: ...
TESTS:
sage: s = lambda (x,y,z) : x**2 + y**2 + z**2
sage: for ijk in Subsets(Subsets(35000,15).random_element(),3):
....: if s(three_squares_pyx(s(ijk))) != s(ijk):
....: print "hey"
Return a pair of non-negative integers (i,j) such that .
If n is not a sum of two squares, a ValueError is raised. The input
must be lesser than , otherwise an OverflowError is
raised.
See also
two_squares() is much more suited for large inputs
EXAMPLES:
sage: from sage.rings.sum_of_squares import two_squares_pyx
sage: two_squares_pyx(0)
(0, 0)
sage: two_squares_pyx(1)
(0, 1)
sage: two_squares_pyx(2)
(1, 1)
sage: two_squares_pyx(3)
Traceback (most recent call last):
...
ValueError: 3 is not a sum of 2 squares
sage: two_squares_pyx(106)
(5, 9)
sage: two_squares_pyx(2**32)
Traceback (most recent call last):
...
OverflowError: ...
TESTS:
sage: s = lambda (x,y) : x**2 + y**2
sage: for ij in Subsets(Subsets(45000,15).random_element(),2):
....: if s(two_squares_pyx(s(ij))) != s(ij):
....: print "hey"
sage: for n in xrange(1,65536):
....: if two_squares_pyx(n**2) != (0, n):
....: print "hey"
....: if two_squares_pyx(n**2+1) != (1, n):
....: print "ho"