Optimized `mulDiv` alternatives for special cases

[3sGgpQ8H]

🧐 Motivation
The mulDiv function defined in Math.sol is very efficient in a generic case, but for specific cases better approaches could exist. Consider implementing optimized mulDiv alternatives for special cases.

📝 Details
Add the following functions to Math.sol:

1. mulDivFull(uint x, uint y, uint denominator) returns (uint): like mulDiv but always does full division, skipping the prod1 == 0 check; useful for cases where x*y is very unlikely to fit into 256 bits.
2. mulDivStatic(uint x, uint y, uint denominator, uint twos, uint inverse) returns (uint): like mulDiv but accepts the twos and inverse values as arguments, instead of than calculates them; useful for cases where denominator is a constant or where the same denominator is used many times. Also consider a separate function to calculate twos and inverse for a given denominator.
3. shlDiv(uint x, uint sh, uint denominator) returns (uint): like mulDiv but performs left shift instead of multiplication; useful for cases where one of the factors is a known power of two. Also consider functions shlDivFull and shlDivStatic.
4. mulShr(uint x, uint y, uint sh) returns (uint): like mulDiv but performs right shift instead of division; useful for cases where denominator is a known power of two. Also consider function mulShrFull.
5. mulDiv128(uint x, uint y, uint128 denominator) returns (uint): like mulDiv but with 128-bit denominator, which more efficient implementation (https://medium.com/coinmonks/math-in-solidity-part-3-percents-and-proportions-4db014e080b1#4821); useful for cases where denominator is guaranteed to fit into 128 bits.

[Amxx]

Hello @3sGgpQ8H and thank you for the suggestion.

I understand that there may be cases where these variant would be more effective, but having multiple implementation of the mulDiv logic would decreass the discoverability for the users.

Variant 1 for example (mulDivFull) would only save a small check that is probable <20gas. On the other hand, that is one more version we have to test and maintain. We also have to verify that there wouldn't be any issue if the parameters result in prod1 == 0.

We'll keep you demands in mind, but unless other users request similar features, with clear usecase, its not something we will prioritize.

@ernestognw WDYT?

[ernestognw]

Thanks for the thorough list @3sGgpQ8H!

I agree with Hadrien in that multiple implementations of mulDiv not only decrease discoverability but also confuse users in my opinion. For example, a regular user (not a Solidity degen) will be at risk of picking mulDivFull without realizing the documentation notes about the size of the inputs.

I like the idea of generalizing the function, though, I'd like the implementation to be more straightforward (perhaps a base mulDiv with just a couple of variants).

Also, it'd be great to benchmark the differences, as Hadrien said, ~20 gas units are low (in order of magnitude) so we'd rather keep the DX as secure as possible.