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 code
  • d – 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 length len.

INPUT:

  • p – a polynomial
  • len – an integer. If len is smaller than the degree of p, the returned list will be of size degree of p, else it will be of size len.

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 and c – 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)