Repository: osmosis-labs/osmosis
Pull request #3809 (2022-12-21 01:33:17)

feat(x/twap): use exp2 in twapPow; add overflow test
<!-- < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < ☺
v                               ✰  Thanks for creating a PR! ✰    
v    Before smashing the submit button please review the checkboxes.
v    If a checkbox is n/a - please still include it but + a little note why
v    If your PR doesn't close an issue, that's OK!  Just remove the Closes: #XXX line!
☺ > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >  -->

Closes: #3540 

## What is the purpose of the change

This PR switches to use the new `Exp2` function (#3708) in x/twap for computing geometric twap.

It also adds a test at max spot price, showing that there is no overflow.

## Testing and Verifying

This change added overflow test and refactored twap math function tests to be simpler.

Note that adding more hand-calculated tests is tracked in: https://github.com/osmosis-labs/osmosis/issues/3541

On top of this PR, I made a PR with query tests that currently pass: https://github.com/osmosis-labs/osmosis/pull/3802

## Documentation and Release Note

  - Does this pull request introduce a new feature or user-facing behavior changes? no
  - Is a relevant changelog entry added to the `Unreleased` section in `CHANGELOG.md`? no
  - How is the feature or change documented? not applicable

ValarDragon: amazing the TWAP time spent in pow has 10x decreased, great sign for our Exp2 fn :)

Patch:
diff --git a/CHANGELOG.md b/CHANGELOG.md
index a84e6939b..c54599b01 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -51,6 +51,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0
 * [#3678](https://github.com/osmosis-labs/osmosis/pull/3678) implement mutative `PowerIntegerMut` function on `osmomath.BigDec`.
 * [#3708](https://github.com/osmosis-labs/osmosis/pull/3708) `Exp2` function to compute 2^decimal.
 * [#3693](https://github.com/osmosis-labs/osmosis/pull/3693) Add `EstimateSwapExactAmountOut` query to stargate whitelist
+* [#3731](https://github.com/osmosis-labs/osmosis/pull/3731) BigDec Power functions with decimal exponent.
 
 ### API breaks
 
diff --git a/osmomath/decimal.go b/osmomath/decimal.go
index 955b6229f..a5735a55e 100644
--- a/osmomath/decimal.go
+++ b/osmomath/decimal.go
@@ -997,3 +997,39 @@ func (d BigDec) PowerIntegerMut(power uint64) BigDec {
 
 	return d.MulMut(tmp)
 }
+
+// Power returns a result of raising the given big dec to
+// a positive decimal power. Panics if the power is negative.
+// Panics if the base is negative. Does not mutate the receiver.
+// The max supported exponent is defined by the global maxSupportedExponent.
+// If a greater exponent is given, the function panics.
+// The error is not bounded but expected to be around 10^-18, use with care.
+// See the underlying Exp2, LogBase2 and Mul for the details of their bounds.
+func (d BigDec) Power(power BigDec) BigDec {
+	if d.IsNegative() {
+		panic(fmt.Sprintf("negative base is not supported for Power(), base was (%s)", d))
+	}
+	if power.IsNegative() {
+		panic(fmt.Sprintf("negative power is not supported for Power(), power was (%s)", power))
+	}
+	if power.Abs().GT(maxSupportedExponent) {
+		panic(fmt.Sprintf("integer exponent %s is too large, max (%s)", power, maxSupportedExponent))
+	}
+	if power.IsInteger() {
+		return d.PowerInteger(power.TruncateInt().Uint64())
+	}
+	if power.IsZero() {
+		return OneDec()
+	}
+	if d.IsZero() {
+		return ZeroDec()
+	}
+	if d.Equal(twoBigDec) {
+		return Exp2(power)
+	}
+
+	// d^power = exp2(power * log_2{base})
+	result := Exp2(d.LogBase2().Mul(power))
+
+	return result
+}
diff --git a/x/twap/logic.go b/x/twap/logic.go
index 63c824c6e..fdf8586fe 100644
--- a/x/twap/logic.go
+++ b/x/twap/logic.go
@@ -11,15 +11,6 @@ import (
 	"github.com/osmosis-labs/osmosis/v13/x/twap/types"
 )
 
-// geometricTwapMathBase is the base used for geometric twap calculation
-// in logarithm and power math functions.
-// See twapLog and computeGeometricTwap functions for more details.
-var (
-	geometricTwapMathBase = sdk.NewDec(2)
-	// TODO: analyze choice.
-	geometricTwapPowPrecision = sdk.MustNewDecFromStr("0.00000001")
-)
-
 func newTwapRecord(k types.AmmInterface, ctx sdk.Context, poolId uint64, denom0, denom1 string) (types.TwapRecord, error) {
 	denom0, denom1, err := types.LexicographicalOrderDenoms(denom0, denom1)
 	if err != nil {
@@ -268,13 +259,15 @@ func computeTwap(startRecord types.TwapRecord, endRecord types.TwapRecord, quote
 }
 
 // twapLog returns the logarithm of the given spot price, base 2.
-// TODO: basic test
 func twapLog(price sdk.Dec) sdk.Dec {
 	return osmomath.BigDecFromSDKDec(price).LogBase2().SDKDec()
 }
 
-// twapPow exponentiates the geometricTwapMathBase to the given exponent.
-// TODO: basic test and benchmark.
+// twapPow exponentiates 2 to the given exponent.
 func twapPow(exponent sdk.Dec) sdk.Dec {
-	return osmomath.PowApprox(geometricTwapMathBase, exponent, geometricTwapPowPrecision)
+	exp2 := osmomath.Exp2(osmomath.BigDecFromSDKDec(exponent.Abs()))
+	if exponent.IsNegative() {
+		return osmomath.OneDec().Quo(exp2).SDKDec()
+	}
+	return exp2.SDKDec()
 }
diff --git a/x/twap/strategy.go b/x/twap/strategy.go
index ecbdd4d47..bf3039a7e 100644
--- a/x/twap/strategy.go
+++ b/x/twap/strategy.go
@@ -2,7 +2,11 @@ package twap
 
 import (
 	sdk "github.com/cosmos/cosmos-sdk/types"
+
+	"github.com/osmosis-labs/osmosis/v13/osmomath"
 	"github.com/osmosis-labs/osmosis/v13/x/twap/types"
+
+	gammtypes "github.com/osmosis-labs/osmosis/v13/x/gamm/types"
 )
 
 // twapStrategy is an interface for computing TWAPs.
@@ -42,11 +46,14 @@ func (s *geometric) computeTwap(startRecord types.TwapRecord, endRecord types.Tw
 	timeDelta := endRecord.Time.Sub(startRecord.Time)
 	arithmeticMeanOfLogPrices := types.AccumDiffDivDuration(accumDiff, timeDelta)
 
-	geometricMeanDenom0 := twapPow(arithmeticMeanOfLogPrices)
+	result := twapPow(arithmeticMeanOfLogPrices)
 	// N.B.: Geometric mean of recprocals is reciprocal of geometric mean.
 	// https://proofwiki.org/wiki/Geometric_Mean_of_Reciprocals_is_Reciprocal_of_Geometric_Mean
 	if quoteAsset == startRecord.Asset1Denom {
-		return sdk.OneDec().Quo(geometricMeanDenom0)
+		result = sdk.OneDec().Quo(result)
 	}
-	return geometricMeanDenom0
+
+	// N.B. we round because this is the max number of significant figures supported
+	// by the underlying spot price function.
+	return osmomath.SigFigRound(result, gammtypes.SpotPriceSigFigs)
 }


Test patch:
diff --git a/osmomath/decimal_test.go b/osmomath/decimal_test.go
index a33e08647..c90d6872c 100644
--- a/osmomath/decimal_test.go
+++ b/osmomath/decimal_test.go
@@ -12,6 +12,7 @@ import (
 	"github.com/stretchr/testify/suite"
 	"gopkg.in/yaml.v2"
 
+	"github.com/osmosis-labs/osmosis/v13/app/apptesting/osmoassert"
 	"github.com/osmosis-labs/osmosis/v13/osmomath"
 	gammtypes "github.com/osmosis-labs/osmosis/v13/x/gamm/types"
 )
@@ -20,6 +21,12 @@ type decimalTestSuite struct {
 	suite.Suite
 }
 
+var (
+	zeroAdditiveErrTolerance = osmomath.ErrTolerance{
+		AdditiveTolerance: sdk.ZeroDec(),
+	}
+)
+
 func TestDecimalTestSuite(t *testing.T) {
 	suite.Run(t, new(decimalTestSuite))
 }
@@ -1144,9 +1151,18 @@ func (s *decimalTestSuite) TestPowerInteger() {
 				tolerance = tc.expectedToleranceOverwrite
 			}
 
+			// Main system under test
 			actualResult := tc.base.PowerInteger(tc.exponent)
 			require.True(osmomath.DecApproxEq(s.T(), tc.expectedResult, actualResult, tolerance))
 
+			// Secondary system under test.
+			// To reduce boilerplate from the same test cases when exponent is a
+			// positive integer, we also test Power().
+			// Negative exponent and base are not supported for Power()
+			if tc.exponent >= 0 && !tc.base.IsNegative() {
+				actualResult2 := tc.base.Power(osmomath.NewDecFromInt(osmomath.NewIntFromUint64(tc.exponent)))
+				require.True(osmomath.DecApproxEq(s.T(), tc.expectedResult, actualResult2, tolerance))
+			}
 		})
 	}
 }
@@ -1219,7 +1235,7 @@ func (s *decimalTestSuite) TestMul_Mutation() {
 	}
 }
 
-// TestMul_Mutation tests that PowerIntegerMut mutates the receiver
+// TestPowerInteger_Mutation tests that PowerIntegerMut mutates the receiver
 // while PowerInteger is not.
 func (s *decimalTestSuite) TestPowerInteger_Mutation() {
 
@@ -1260,3 +1276,114 @@ func (s *decimalTestSuite) TestPowerInteger_Mutation() {
 		})
 	}
 }
+
+func (s *decimalTestSuite) TestPower() {
+	tests := map[string]struct {
+		base           osmomath.BigDec
+		exponent       osmomath.BigDec
+		expectedResult osmomath.BigDec
+		expectPanic    bool
+		errTolerance   osmomath.ErrTolerance
+	}{
+		// N.B.: integer exponents are tested under TestPowerInteger.
+
+		"3 ^ 2 = 9 (integer base and integer exponent)": {
+			base:     osmomath.NewBigDec(3),
+			exponent: osmomath.NewBigDec(2),
+
+			expectedResult: osmomath.NewBigDec(9),
+
+			errTolerance: zeroAdditiveErrTolerance,
+		},
+		"2^0.5 (base of 2 and non-integer exponent)": {
+			base:     osmomath.MustNewDecFromStr("2"),
+			exponent: osmomath.MustNewDecFromStr("0.5"),
+
+			// https://www.wolframalpha.com/input?i=2%5E0.5+37+digits
+			expectedResult: osmomath.MustNewDecFromStr("1.414213562373095048801688724209698079"),
+
+			errTolerance: osmomath.ErrTolerance{
+				AdditiveTolerance: minDecTolerance,
+				RoundingDir:       osmomath.RoundDown,
+			},
+		},
+		"3^0.33 (integer base other than 2 and non-integer exponent)": {
+			base:     osmomath.MustNewDecFromStr("3"),
+			exponent: osmomath.MustNewDecFromStr("0.33"),
+
+			// https://www.wolframalpha.com/input?i=3%5E0.33+37+digits
+			expectedResult: osmomath.MustNewDecFromStr("1.436977652184851654252692986409357265"),
+
+			errTolerance: osmomath.ErrTolerance{
+				AdditiveTolerance: minDecTolerance,
+				RoundingDir:       osmomath.RoundDown,
+			},
+		},
+		"e^0.98999 (non-integer base and non-integer exponent)": {
+			base:     osmomath.EulersNumber,
+			exponent: osmomath.MustNewDecFromStr("0.9899"),
+
+			// https://www.wolframalpha.com/input?i=e%5E0.9899+37+digits
+			expectedResult: osmomath.MustNewDecFromStr("2.690965362357751196751808686902156603"),
+
+			errTolerance: osmomath.ErrTolerance{
+				AdditiveTolerance: minDecTolerance,
+				RoundingDir:       osmomath.RoundUnconstrained,
+			},
+		},
+		"10^0.001 (small non-integer exponent)": {
+			base:     osmomath.NewBigDec(10),
+			exponent: osmomath.MustNewDecFromStr("0.001"),
+
+			// https://www.wolframalpha.com/input?i=10%5E0.001+37+digits
+			expectedResult: osmomath.MustNewDecFromStr("1.002305238077899671915404889328110554"),
+
+			errTolerance: osmomath.ErrTolerance{
+				AdditiveTolerance: minDecTolerance,
+				RoundingDir:       osmomath.RoundUnconstrained,
+			},
+		},
+		"13^100.7777 (large non-integer exponent)": {
+			base:     osmomath.NewBigDec(13),
+			exponent: osmomath.MustNewDecFromStr("100.7777"),
+
+			// https://www.wolframalpha.com/input?i=13%5E100.7777+37+digits
+			expectedResult: osmomath.MustNewDecFromStr("1.822422110233759706998600329118969132").Mul(osmomath.NewBigDec(10).PowerInteger(112)),
+
+			errTolerance: osmomath.ErrTolerance{
+				MultiplicativeTolerance: minDecTolerance,
+				RoundingDir:             osmomath.RoundDown,
+			},
+		},
+		"large non-integer exponent with large non-integer base - panics": {
+			base:     osmomath.MustNewDecFromStr("169.137"),
+			exponent: osmomath.MustNewDecFromStr("100.7777"),
+
+			expectPanic: true,
+		},
+		"negative base - panic": {
+			base:     osmomath.NewBigDec(-3),
+			exponent: osmomath.MustNewDecFromStr("4"),
+
+			expectPanic: true,
+		},
+		"negative exponent - panic": {
+			base:     osmomath.NewBigDec(1),
+			exponent: osmomath.MustNewDecFromStr("-4"),
+
+			expectPanic: true,
+		},
+	}
+
+	for name, tc := range tests {
+		tc := tc
+		s.Run(name, func() {
+			osmoassert.ConditionalPanic(s.T(), tc.expectPanic, func() {
+
+				actualResult := tc.base.Power(tc.exponent)
+
+				s.Require().Equal(0, tc.errTolerance.CompareBigDec(tc.expectedResult, actualResult))
+			})
+		})
+	}
+}
diff --git a/tests/localosmosis/scripts/setup.sh b/tests/localosmosis/scripts/setup.sh
index 7e275ff87..156517c98 100755
--- a/tests/localosmosis/scripts/setup.sh
+++ b/tests/localosmosis/scripts/setup.sh
@@ -55,8 +55,8 @@ edit_genesis () {
     dasel put string -f $GENESIS '.app_state.mint.params.mint_denom' "uosmo"
     dasel put string -f $GENESIS '.app_state.mint.params.epoch_identifier' "day"
 
-    # Update gamm module
-    dasel put string -f $GENESIS '.app_state.gamm.params.pool_creation_fee.[0].denom' "uosmo"
+    # Update swaprouter module
+    dasel put string -f $GENESIS '.app_state.swaprouter.params.pool_creation_fee.[0].denom' "uosmo"
 
     # Update txfee basedenom
     dasel put string -f $GENESIS '.app_state.txfees.basedenom' "uosmo"
diff --git a/x/twap/export_test.go b/x/twap/export_test.go
index d9483f059..1ccbbd47a 100644
--- a/x/twap/export_test.go
+++ b/x/twap/export_test.go
@@ -15,8 +15,6 @@ type (
 	GeometricTwapStrategy  = geometric
 )
 
-var GeometricTwapMathBase = geometricTwapMathBase
-
 func (k Keeper) StoreNewRecord(ctx sdk.Context, record types.TwapRecord) {
 	k.storeNewRecord(ctx, record)
 }
diff --git a/x/twap/logic_test.go b/x/twap/logic_test.go
index 4ff239d6d..28c44cbb0 100644
--- a/x/twap/logic_test.go
+++ b/x/twap/logic_test.go
@@ -3,7 +3,6 @@ package twap_test
 import (
 	"errors"
 	"fmt"
-	"math"
 	"testing"
 	"time"
 
@@ -1319,30 +1318,34 @@ func (s *TestSuite) TestComputeArithmeticTwapWithSpotPriceError() {
 	}
 }
 
-func (s *TestSuite) TestTwapLog() {
-	var expectedErrTolerance = osmomath.MustNewDecFromStr("0.000000000000000100")
-	// "Twaplog{912648174127941279170121098210.928219201902041311} = 99.525973560175362367"
-	// From: https://www.wolframalpha.com/input?i2d=true&i=log+base+2+of+912648174127941279170121098210.928219201902041311+with+20+digits
-	var priceValue = osmomath.MustNewDecFromStr("912648174127941279170121098210.928219201902041311")
-	var expectedValue = osmomath.MustNewDecFromStr("99.525973560175362367")
-
-	result := twap.TwapLog(priceValue.SDKDec())
-	result_by_customBaseLog := priceValue.CustomBaseLog(osmomath.BigDecFromSDKDec(twap.GeometricTwapMathBase))
-	s.Require().True(expectedValue.Sub(osmomath.BigDecFromSDKDec(result)).Abs().LTE(expectedErrTolerance))
-	s.Require().True(result_by_customBaseLog.Sub(osmomath.BigDecFromSDKDec(result)).Abs().LTE(expectedErrTolerance))
+// TestTwapLog_CorrectBase tests that the base of 2 is used for the twap log function.
+// log_2{16} = 4
+func (s *TestSuite) TestTwapLog_CorrectBase() {
+	logOf := sdk.NewDec(16)
+	expectedValue := sdk.NewDec(4)
+
+	result := twap.TwapLog(logOf)
+
+	s.Require().Equal(expectedValue, result)
 }
 
-func (s *TestSuite) TestTwapPow() {
-	var expectedErrTolerance = osmomath.MustNewDecFromStr("0.00000100")
-	// "TwapPow(0.5) = 1.41421356"
-	// From: https://www.wolframalpha.com/input?i2d=true&i=power+base+2+exponent+0.5+with+9+digits
-	exponentValue := osmomath.MustNewDecFromStr("0.5")
-	expectedValue := osmomath.MustNewDecFromStr("1.41421356")
+// TestTwapPow_CorrectBase tests that the base of 2 is used for the twap power function.
+// 2^3 = 8
+func (s *TestSuite) TestTwapPow_CorrectBase() {
+	exponentValue := osmomath.NewBigDec(3)
+	expectedValue := sdk.NewDec(8)
 
 	result := twap.TwapPow(exponentValue.SDKDec())
-	result_by_mathPow := math.Pow(twap.GeometricTwapMathBase.MustFloat64(), exponentValue.SDKDec().MustFloat64())
-	s.Require().True(expectedValue.Sub(osmomath.BigDecFromSDKDec(result)).Abs().LTE(expectedErrTolerance))
-	s.Require().True(osmomath.MustNewDecFromStr(fmt.Sprint(result_by_mathPow)).Sub(osmomath.BigDecFromSDKDec(result)).Abs().LTE(expectedErrTolerance))
+
+	s.Require().Equal(expectedValue, result)
+}
+
+// TestTwapPow_NegativeExponent tests that twap pow can handle a negative exponent
+// 2^-1 = 0.5
+func (s *TestSuite) TestTwapPow_NegativeExponent() {
+	expectedResult := sdk.MustNewDecFromStr("0.5")
+	result := twap.TwapPow(oneDec.Neg())
+	s.Require().Equal(expectedResult, result)
 }
 
 func testCaseFromDeltas(s *TestSuite, startAccum, accumDiff sdk.Dec, timeDelta time.Duration, expectedTwap sdk.Dec) computeTwapTestCase {
diff --git a/x/twap/strategy_test.go b/x/twap/strategy_test.go
index d4f4d5299..be3e86128 100644
--- a/x/twap/strategy_test.go
+++ b/x/twap/strategy_test.go
@@ -7,6 +7,7 @@ import (
 
 	"github.com/osmosis-labs/osmosis/v13/app/apptesting/osmoassert"
 	"github.com/osmosis-labs/osmosis/v13/osmomath"
+	gammtypes "github.com/osmosis-labs/osmosis/v13/x/gamm/types"
 	"github.com/osmosis-labs/osmosis/v13/x/twap"
 	"github.com/osmosis-labs/osmosis/v13/x/twap/types"
 )
@@ -21,6 +22,10 @@ type computeTwapTestCase struct {
 	expPanic       bool
 }
 
+var (
+	oneHundredYears = OneSec.MulInt64(60 * 60 * 24 * 365 * 100)
+)
+
 // TestComputeArithmeticTwap tests computeTwap on various inputs.
 // The test vectors are structured by setting up different start and records,
 // based on time interval, and their accumulator values.
@@ -300,3 +305,19 @@ func (s *TestSuite) TestComputeGeometricStrategyTwap_ThreeAsset() {
 		})
 	}
 }
+
+// TestTwapPow_MaxSpotPrice_NoOverflow tests that no overflow occurs at log_2{max spot price values}.
+// and that the epsilon is within the tolerated multiplicative error.
+func (s *TestSuite) TestTwapLogPow_MaxSpotPrice_NoOverflow() {
+	errTolerance := osmomath.ErrTolerance{
+		MultiplicativeTolerance: sdk.OneDec().Quo(sdk.NewDec(10).Power(18)),
+		RoundingDir:             osmomath.RoundDown,
+	}
+
+	oneHundredYearsTimesMaxSpotPrice := oneHundredYears.Mul(gammtypes.MaxSpotPrice)
+
+	exponentValue := twap.TwapLog(oneHundredYearsTimesMaxSpotPrice)
+	finalValue := twap.TwapPow(exponentValue)
+
+	s.Require().Equal(0, errTolerance.CompareBigDec(osmomath.BigDecFromSDKDec(oneHundredYearsTimesMaxSpotPrice), osmomath.BigDecFromSDKDec(finalValue)))
+}