feat(avm): bounded mle implementation

[jeanmon]

Resolves #8651

[fcarreiro]

Do you need to be explicit about dynamic extent? From https://en.cppreference.com/w/cpp/container/span it looks like it's the default, that'd mean you could do std::span<const Fr> truncated_points = evaluation_points.first(dim);

Also I wonder, do you need this function?
Cant you use the existing partial_evaluate_mle or evaluate_mle and create a span in the caller doing exactly std::span<const Fr> truncated_points = evaluation_points.first(dim); and passing that?

[ledwards2225]

Sort of along the lines of what @fcarreiro is saying, I wonder if this should just become the default behavior of evaluate_mle. Instead of explicitly providing a dim the function could just compute something like dim = msb(poly.start_offset() + size()) + 1 then perform the logic you've laid out here. This would in theory lead to even better efficiency unless your polys always have dim = AVM_PUBLIC_COLUMN_MAX_SIZE_LOG. In this case your tests could compare two equivalent polys, one of which takes advantage of Adams new structured poly and one of which doesn't.

[jeanmon]

@fcarreiro You are right, I will the remove the explicit std::dynamic_extent

[jeanmon]

@ledwards2225 @fcarreiro I think it makes complete sense to adapt the standard evaluate_mle . It seems that this algorithm was ported from LegacyPolynomials which did not have the concept of virtual_size(). So, Polynomials class could not only leverage the memory gain (collapsing all tail zeros) but algorithmically whenever we can.
This way any caller would benefit from a "bounded" MLE. Using the constructor of Polynomials in a natural way, a caller would not oversize size() more than necessary.

[ledwards2225]

LGTM. Made a suggestion to simply make this the default behavior of evaluate_mle with an auto computed dim

[ledwards2225]

Sort of along the lines of what @fcarreiro is saying, I wonder if this should just become the default behavior of evaluate_mle. Instead of explicitly providing a dim the function could just compute something like dim = msb(poly.start_offset() + size()) + 1 then perform the logic you've laid out here. This would in theory lead to even better efficiency unless your polys always have dim = AVM_PUBLIC_COLUMN_MAX_SIZE_LOG. In this case your tests could compare two equivalent polys, one of which takes advantage of Adams new structured poly and one of which doesn't.