msm_in_circuit_cost.py

class OpCosts:
    def __init__(self, select, add, double):

        self.select = select
        self.add = add
        self.double = double


def estimate_windowed(B, w, n, costs: OpCosts):
    c_prepare_table = (2**w) * costs.add
    c_acc = (B // w) * costs.add
    c_doubling = (B // n) * costs.double
    c_table_get = B * costs.select
    return c_prepare_table + c_acc + c_doubling + c_table_get


def estimate_bucket(B, w, n, costs: OpCosts):
    c_doubling = (B // n) * costs.double
    c_acc = (B // w) * costs.add
    c_table = (2 * B) * costs.select

    u = B * (2 ** (w + 1))
    v = w * n
    c_bucket_sum = (u // v) * costs.add

    return c_doubling + c_acc + c_table + c_bucket_sum


model = OpCosts(1, 1, 1)
B = 256
w_upto = 20
n = 1 << 19
number_of_columns = 6


print("window")
for w in range(1, w_upto):
    scalar_composition_overhead = (B // w) // number_of_columns
    cost = estimate_windowed(B, w, n, model)
    print(w, cost + scalar_composition_overhead)

print("bucket")
scalar_composition_overhead = 0
for w in range(1, w_upto):
    scalar_composition_overhead = (B // w) // number_of_columns
    cost = estimate_bucket(B, w, n, model)
    print(w, cost + scalar_composition_overhead)