fastcrypto icon indicating copy to clipboard operation
fastcrypto copied to clipboard

Reduce the number subtractions in `get_lagrange_coefficients` by half

Open jonas-lj opened this issue 1 year ago • 1 comments

It's possible to cache the n^2 differences computed in get_lagrange_coefficients and use this to reduce the number of subtractions by half.

I'm not sure this is a bottleneck as it is, but I did some profiling with 1000 indices and here, about 20-25% of the time is spent on the subtractions.

@benr-ml Feel free to use this if you think it's needed, otherwise you can just close the PR.

jonas-lj avatar Sep 30 '23 22:09 jonas-lj

Great idea! Since in practice we compute those coefficients for the same set of parties many times, I wonder if we should generate the cache in a preprocessing stage and just pass it as an optional input. Let me think about that...

benr-ml avatar Oct 01 '23 07:10 benr-ml