Optimization idea: using scaling instead of doubling in Strauss-Shamir

[nalinbhardwaj]

Instead of doubling at each index of the loop, for the bits that are 0 in both u and v we can skip over them while incrementing some counter. When we encounter the next non-zero bit (or the end of the loop), we can perform a single scaling of 2^(counter) on the running sum point. Should reduce cost since scaling can be implemented more gas efficiently than (counter) doubles.

Don’t see other implementations do this probably because scaling cost is close enough in real CPU cycles to double and add, but our use case of Solidity would see improvements I believe.

[ameya-deshmukh]

@nalinbhardwaj is this something you're interested in now as well? I'll be keen to explore it if that's the case, lmk :)