Closed cyphar closed 2 years ago
Implemented in e50d07998793cdcde246d7c60290cb94d012a4a4.
After doing some benchmarking it turns out the previous expansion code we were using seems to have had exponential time complexity due to the need to do binomial expansions (it might have even been factorial, I'm not sure). The barycentric form is so much more efficient -- 256-threshold scheme only takes 3.39s with --release
and 78.08s in debug mode to do the expansion. For reference, even in --release
mode it took 119s to do a 20-threshold expansion with the old method.
Recovering the full polynomial is a neat party trick but is not necessary for quorom expansion because we can just evaluate the X values we'd like. However in order to do this efficiently we need to make use of the barycentric form of the Lagrange polynomials so we can evaluate multiple X values more efficiently.