[osmoutils]: Add tests with different upper/lower bounds to osmoutil binary search

[AlpinYukseloglu]

Background

Ref: https://github.com/osmosis-labs/osmosis/pull/2802#discussion_r975861292

We should test our binary search implementation(s) on different bounds (currently all of them use the same min and max value).

Suggested Design

Cases to add:

• Nonzero lower bounds
• Equivalent upper and lower bounds (should panic)
• Lower bound greater than upper bound (should panic)
• Negative bounds (should panic)
• Overflowing bounds (should panic)
• Different upper bounds (just so all the tests aren't identical)

Acceptance Criteria

• Most/all of the cases above are added and pass

[pysel]

I was working on this issue: every test case seemed fine and passed fine except for this one:

"different upper bounds":     {cubicF, osmomath.OneDec(), osmomath.NewBigDec(1 << 10), osmomath.NewBigDec(1 + (1 << 25)), lowErrTolerance, 20000, false},

So basically the problem is when you specify upperbounds (3rd struct field) to be less than 1 << 49 it throws this error:

 hit maximum iterations, did not converge fast enough

As seen from this test case, I tried increasing the maxIterations field (20000), however, it did not work.

PS: I removed actualSolvedInput field from tests map, so now test routine looks like this:

        actualSolvedInput, err := BinarySearchBigDec(tc.f, tc.lowerbound, tc.upperbound, tc.targetOutput, tc.errTolerance,         tc.maxIterations)

	if tc.expectErr {
		require.Error(t, err)
	} else {
		require.NoError(t, err)
		output, err := tc.f(actualSolvedInput)
		require.NoError(t, err)

		require.Equal(t, tc.errTolerance.CompareBigDec(output, tc.targetOutput), 0) // 0 - within errTolerance
	}

[AlpinYukseloglu]

Do you have your work on a fork/branch by any chance? The likeliest scenario is that the values being considered were too large for even our BigDec precision, preventing the search from ever converging (if this is the case then it would have triggered an infinite loop so increasing maxIterations wouldn't do anything)

If this is the case then it is intended behavior as precision will always be a bottleneck for sufficiently large binary search inputs, but worth exploring just in case!

[pysel]

Yes, I do: https://github.com/RusAkh/osmosis-fork (branch name is issue2807). However, I forgot to mention that if you specify an upper bound in this range [1 << 49; 1 << 62] it passes as expected (more than 1 << 62 is out of bounds for int64).

[pysel]

I checked this issue again. So it seems that the error was in cubicF function itself. It looked like this:

cubicF := func(a osmomath.BigDec) (osmomath.BigDec, error) {
		calculation := a.Quo(osmomath.NewBigDec(10).Power(18))
		result := calculation.Power(3)
		output := result.Mul(osmomath.NewBigDec(10).Power(18))
		return output, nil
	}

it was returning incorrect outputs. For example, for this line:

fmt.Println(cubicF(osmomath.NewBigDec(3)))

an output was 0.000000000000000000000000000000000000 <nil>

Basically, now it looks like this and works fine:

cubicF := func(a osmomath.BigDec) (osmomath.BigDec, error) {
		calculation := a.Power(3)
		result := calculation.Quo(osmomath.NewBigDec(10).Power(18))
		output := result.Mul(osmomath.NewBigDec(10).Power(18))
		return output, nil
	}

[AlpinYukseloglu]

Closing this since it is non v13 blocking