Optimize sqrt

[chipshort]

ilog is supported now, so we can calculate the square root more efficiently

https://github.com/CosmWasm/cosmwasm/blob/a34949b861dfa11ec8016b468922e48e6a6d785d/packages/std/src/math/decimal.rs#L360C12-L360C12

[chipshort]

I ran some more gas benchmarks with different implementations.
All of those were run based on the changes in #2108 (it improves the numbers quite drastically)

• sqrt is the old implementation
• sqrt2 is [0, 1, 2, 3, 4, 5, 6, 7, 8, 9].binary_search_by with an additional memoization array
• sqrt3 is unrolled binary search (check 5, if it doesn't work check 2, etc., a few nested matches)
• sqrt4 is the version where we directly calculate the max precision using the log (the one in Optimize sqrts #2029)

Decimal	sqrt	sqrt2	sqrt3	sqrt4	rel. diff sqrt2	rel. diff sqrt3	rel. diff sqrt4
1.0	5519700	9529650	8362650	5911650	73%	52%	7%
2*10^(-18)	4996200	5901600	5590500	5181600	18%	12%	4%
MAX	5830500	5270100	5224500	5013750	-10%	-10%	-14%
0.01	6042000	9698400	8491050	6463800	61%	41%	7%

Decimal256	sqrt	sqrt2	sqrt3	sqrt4	rel. diff sqrt2	rel. diff sqrt3	rel. diff sqrt4
1.0	7360800	17133150	14003850	11520450	133%	90%	57%
2*10^(-18)	6631650	12610950	10519650	10778250	90%	59%	63%
MAX	16030950	11466600	11555100	9880650	-28%	-28%	-38%
0.01	8113650	17565750	14318700	12258600	116%	76%	51%

None of these strike me as particularly worthwhile, so I think we can close this.

[webmaster128]

Great stuff, thank you!