Guruswami-Sudan utility methods¶
AUTHORS:
Johan S. R. Nielsen, original implementation (see [Nie] for details)
David Lucas, ported the original implementation in Sage
-
sage.coding.guruswami_sudan.utils.
gilt
(x)¶ Returns the greatest integer smaller than
x
.EXAMPLES:
sage: from sage.coding.guruswami_sudan.utils import gilt sage: gilt(43) 42
It works with any type of numbers (not only integers):
sage: gilt(43.041) 43
-
sage.coding.guruswami_sudan.utils.
johnson_radius
(n, d)¶ Returns the Johnson-radius for the code length \(n\) and the minimum distance \(d\).
The Johnson radius is defined as \(n - \sqrt(n(n-d))\).
INPUT:
n
– an integer, the length of the coded
– an integer, the minimum distance of the code
EXAMPLES:
sage: sage.coding.guruswami_sudan.utils.johnson_radius(250, 181) -5*sqrt(690) + 250
-
sage.coding.guruswami_sudan.utils.
ligt
(x)¶ Returns the least integer greater than
x
.EXAMPLES:
sage: from sage.coding.guruswami_sudan.utils import ligt sage: ligt(41) 42
It works with any type of numbers (not only integers):
sage: ligt(41.041) 42
-
sage.coding.guruswami_sudan.utils.
polynomial_to_list
(p, len)¶ Returns
p
as a list of its coefficients of lengthlen
.INPUT:
p
– a polynomiallen
– an integer. Iflen
is smaller than the degree ofp
, the returned list will be of size degree ofp
, else it will be of sizelen
.
EXAMPLES:
sage: from sage.coding.guruswami_sudan.utils import polynomial_to_list sage: F.<x> = GF(41)[] sage: p = 9*x^2 + 8*x + 37 sage: polynomial_to_list(p, 4) [37, 8, 9, 0]
-
sage.coding.guruswami_sudan.utils.
solve_degree2_to_integer_range
(a, b, c)¶ Returns the greatest integer range \([i_1, i_2]\) such that \(i_1 > x_1\) and \(i_2 < x_2\) where \(x_1, x_2\) are the two zeroes of the equation in \(x\): \(ax^2+bx+c=0\).
If there is no real solution to the equation, it returns an empty range with negative coefficients.
INPUT:
a
,b
andc
– coefficients of a second degree equation,a
being the coefficient of the higher degree term.
EXAMPLES:
sage: from sage.coding.guruswami_sudan.utils import solve_degree2_to_integer_range sage: solve_degree2_to_integer_range(1, -5, 1) (1, 4)
If there is no real solution:
sage: solve_degree2_to_integer_range(50, 5, 42) (-2, -1)