Skip to content

simplification: bigfield msub_div constant case handling #1476

@suyash67

Description

@suyash67

tldr: we can simplify/optimise the case when divisor and products in msub_div are constants by adding a new condition. can save a few gates if number of subtractions is large. not a priority at all.

Context: @Sarkoxed found and fixed a bug in madd where we didn't have a special condition handling multiplicands being constant, which led to unused circuit witnesses.

I noticed we don't have similar condition in msub_div for the case when products and divisor are constants. But this isn't a bug (like above) because madd handles the condition on its inputs being constants. It still might be worth just adding a special condition when the multiplicands $(a_1, a_2, \dots, b_1, b_2, \dots)$ and $d$ are circuit-constants when computing:

$$r = \frac{-(a_1 \cdot b_1 + a_2 \cdot b_2 + \dots + a_k \cdot b_k + s_1 + s_2 + \dots + s_\ell)}{d}$$

Specifically, we need something like:

    // If the divisor is constant, we can just compute the result directly
    if (products_constant && divisor.is_constant()) {
        ASSERT(divisor_native != native(0));
        const native divisor_inverse_native = native(1) / divisor_native;

        std::vector<bigfield> to_sub_copy = to_sub;
        const native negative_product_native = -product_native;
        bigfield negative_product(ctx, uint256_t(negative_product_native));
        negative_product.set_origin_tag(new_tag);

        // Add the negative product to the to_sub_copy
        to_sub_copy.push_back(negative_product);
        bigfield to_sub_sum = bigfield::sum(to_sub_copy);
        bigfield numerator = -to_sub_sum;
        return numerator * divisor_inverse_native;
    }

Metadata

Metadata

Assignees

Type

No type

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions