[x/gamm][stableswap]: Investigate critical precision issue with binary search CFMM solver

[AlpinYukseloglu]

Background

Our stableswap implementation has two solver types for our CFMM: a direct solver and a binary search solver. If we can get the latter to work, it would be the better approach for efficiency reasons, but it currently suffers from a precision issue that causes it to loop infinitely in many common scenarios.

The root of the issue is that since binary search solves largest digit -> smallest digit, 10**-18 floating point precision on X affords us 18 digits of precision on k. i.e.:
Expected k: 200000000.000000000000000000
Estimated k: 200000000.000000000887912648

Since our k precision threshold requires at least 10**-10 precision, this fails at anything above k = 100,000,000 = 10^8.

This means that when we try to solve for the change in asset X, we hit the 10**-18 precision cap with at most 10**-9 precision, and since our binary search implementation only terminates upon reaching 10^-10 precision, this causes the solver to run indefinitely.

We should probably make it terminate after 256 iterations as this comment mistakenly claims it does, but I think the issue around precision is an important one to solve regardless so that the solver outputs make sense.

Suggested Design

I believe we have three options to make this work:

1. Decrease precision requirement to allow for k values greater than 10**8 (probably a bad idea & still vulnerable to large ks)
2. Temporarily multiply everything in the binary search by a constant large number like 10**18 to accommodate larger k values
3. Cap the max number of iterations and then output the lower bound for X (marginally inefficient at the trader’s expense but at least removes any security risks due to using binary search over direct solver)

If we cannot make any of these work and do not have any alternative ways to deal with this precision issue, I think we should consider removing/not using the binary search solver for security reasons.

Acceptance Criteria

• All existing tests pass
• Binary search solver doesn't run indefinitely

[catShaark]

I think the problem even worse than you described, the solver seems to me can only accommodate x and y smaller than 10 ^ 3 or so. Let me prove my point here, so the constant function of stable swap is x * y * ( x^2 + y^2 ) = k and we're supposed to guess x_new for a new y_new so that x_new * y_new * ( x_new ^ 2 + y_new ^ 2 ) = k. Let's say our guess of x_new is off from the real x_new by a = 10 ^ -18 because of precision. This means our_k = (x_new + a) * y_new * ( (x_new + a)^2 + y_new ^ 2) = k + insignificantly_small_value + a * ( 3 * x^2 * y + y ^ 3 ). If we want our_k - k < 10 ^ -10 then ( 3 * x^2 * y + y ^ 3 ) should be smaller than 10 ^ 8.

[catShaark]

Given what I said, I still think the binary solver is better cause no matter what tool we use, k value will always end up being off by some large value in the case of large x and y. In other words, what I've proven above is also true for the direct solver. Also, the direct solver touches the root function which is not good right now also due to precision so it might even be less accurate than this binary solver. I think this is something we have to accept as the limitation of sdk.Dec.

[AlpinYukseloglu]

Closed by #2777 and #2778