Implement fast version of decomposition of (small) integers into sum of squares

Implement fast version of decomposition of (small) integers into sum of squares by direct method not relying on factorisation.

AUTHORS:

sage.rings.sum_of_squares.four_squares_pyx(n)

Return a 4-tuple of non-negative integers (i,j,k,l) such that i^2 + j^2
+ k^2 + l^2 = n and i \leq j \leq k \leq l.

The input must be lesser than 2^{32}=4294967296, 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
sage.rings.sum_of_squares.is_sum_of_two_squares_pyx(n)

Return True if n is a sum of two squares and False otherwise.

The input must be smaller than 2^{32} = 4294967296, 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: ...
sage.rings.sum_of_squares.three_squares_pyx(n)

If n is a sum of three squares return a 3-tuple (i,j,k) of Sage integers such that i^2 + j^2 + k^2 = n and i \leq j \leq k. Otherwise raise a ValueError.

The input must be lesser than 2^{32}=4294967296, 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"
sage.rings.sum_of_squares.two_squares_pyx(n)

Return a pair of non-negative integers (i,j) such that i^2 + j^2 = n.

If n is not a sum of two squares, a ValueError is raised. The input must be lesser than 2^{32}=4294967296, 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"

Previous topic

Miscellaneous arithmetic functions

Next topic

Fixing Pickle for Nested Classes

This Page