search

Neptune-Crypto / twenty-first

Collection of mathematics routines and cryptography for the twenty-first century
GNU General Public License v2.0
74 stars 22 forks source link

Speed up various polynomial functions #194

Closed jan-ferdinand closed 7 months ago

jan-ferdinand commented 7 months ago

Mostly engineering, sometimes math, to speed up performance-critical polynomial functions, such as evaluate, interpolate, multiply, etc. Canonical benchmarking target is mjolnir.

coveralls commented 7 months ago

Coverage Status

coverage: 96.541% (+0.07%) from 96.475% when pulling 87a21ee7830b036e3b25d29e720a1ea827384e47 on fast_evaluate into 0ec7453a480279a56d314fef334cc7d82102ce4e on master.

jan-ferdinand commented 7 months ago

There appears to be a measurable difference between the two methods:

Multiplication of Polynomial of Degree 2^1 with a Scalar/Mut/1
                        time:   [4.1544 ns 4.1862 ns 4.2327 ns]
Multiplication of Polynomial of Degree 2^1 with a Scalar/Immut/1
                        time:   [17.486 ns 17.583 ns 17.725 ns]

Multiplication of Polynomial of Degree 2^7 with a Scalar/Mut/7
                        time:   [135.95 ns 136.72 ns 137.65 ns]
Multiplication of Polynomial of Degree 2^7 with a Scalar/Immut/7
                        time:   [142.00 ns 142.95 ns 144.27 ns]

Multiplication of Polynomial of Degree 2^13 with a Scalar/Mut/13
                        time:   [8.4872 µs 8.5008 µs 8.5170 µs]
Multiplication of Polynomial of Degree 2^13 with a Scalar/Immut/13
                        time:   [10.081 µs 10.142 µs 10.221 µs]

I've removed the deprecation, added a benchmark highlighting the performance difference, changed all callers (for which it makes sense) to use the mutable variant, and added documentation.

Interestingly, as far as I can tell, we have not used the method for a while.