Skip to content

Speed up arb_poly_set_coeff_arb in special case #2418

@user202729

Description

@user202729

When an user writes the following code:

for (int i = 0; i < n; i++)
    arb_poly_set_coeff_arb(poly, n, <some expression>)

the user would expect the total complexity to be $O(n)$.

However if <some expression> always return zero, the complexity would be $O(n^2)$.


This is because currently the function is implemented as

void
arb_poly_set_coeff_arb(arb_poly_t poly, slong n, const arb_t x)
{
    arb_poly_fit_length(poly, n + 1);

    if (n + 1 > poly->length)
    {
        _arb_vec_zero(poly->coeffs + poly->length, n - poly->length);
        poly->length = n + 1;
    }

    arb_set(poly->coeffs + n, x);
    _arb_poly_normalise(poly);
}

every time arb_poly_set_coeff_arb is called, it re-zero out the entire length then _arb_poly_normalise shrink it back. This is not ideal.

The fix here is easy:

void
arb_poly_set_coeff_arb(arb_poly_t poly, slong n, const arb_t x)
{
    if (n + 1 > poly->length)
    {
        if (arb_is_zero(x))
            return;
        arb_poly_fit_length(poly, n + 1);
        _arb_vec_zero(poly->coeffs + poly->length, n - poly->length);
        poly->length = n + 1;
    }

    arb_set(poly->coeffs + n, x);
    _arb_poly_normalise(poly);
}

similar for other polynomial types.

of course it won't handle the case where the user repeatedly set some coefficient to nonzero then set it back to zero, but I think this is an unusual use case and can be left for later.


this affects Sage too

R.<x> = CBF[]
%time ignore = R([0]*10000+[1])  # slow
%time ignore = R([1]*10000+[1])  # fast

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions