Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

[stableswap]: Generalize stableswap binary search solver to osmoutils binary search #2794

Closed
Tracked by #1451
AlpinYukseloglu opened this issue Sep 20, 2022 · 0 comments
Closed
Tracked by #1451

[stableswap]: Generalize stableswap binary search solver to osmoutils binary search #2794

AlpinYukseloglu opened this issue Sep 20, 2022 · 0 comments
Assignees
@AlpinYukseloglu
Labels
C:stableswap

Comments

@AlpinYukseloglu
Copy link
Contributor

Background

Factoring out this binary search logic would simplify stableswap solver code drastically and would give us access to a BigDec binary search solver to use elsewhere later if needed

Suggested Design

  • Create a BigDec version of BinarySearch here:

    osmosis/osmoutils/binary_search.go

    Lines 62 to 68 in 0378e54

    func BinarySearch(f func(input sdk.Int) (sdk.Int, error),
    lowerbound sdk.Int,
    upperbound sdk.Int,
    targetOutput sdk.Int,
    errTolerance ErrTolerance,
    maxIterations int,
    ) (sdk.Int, error) {

Acceptance Criteria

  • Binary search unit tests and stableswap tests pass
@AlpinYukseloglu AlpinYukseloglu self-assigned this Sep 20, 2022
@osmo-bot osmo-bot moved this to Needs Review 🔍 in Osmosis Chain Development Sep 20, 2022
@AlpinYukseloglu AlpinYukseloglu mentioned this issue Sep 20, 2022
Closed
55 tasks
@AlpinYukseloglu AlpinYukseloglu changed the title Generalize stableswap binary search solver to osmoutils binary search [stableswap]: Generalize stableswap binary search solver to osmoutils binary search Sep 20, 2022
This was referenced Sep 20, 2022
Merged
Merged
mergify bot pushed a commit that referenced this issue Sep 22, 2022
@AlpinYukseloglu
Implement BigDec binary search in osmoutils (#2802)
b6995ab 
Progress towards: #2794 and #2702

## What is the purpose of the change

This PR implements a `BigDec` binary search function for our general osmoutils package.

## Brief Changelog

- Add `BinarySearchBigDec` to osmoutils
- Add `CompareBigDec` to osmoutils
- Refactor existing and new tests to be more readable (string map names, `t.Run` etc.)

## Testing and Verifying

This change added tests for both new functions in `osmoutils/binary_search_test.go`

## 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 documented)
@AlpinYukseloglu AlpinYukseloglu mentioned this issue Sep 22, 2022
Closed
mergify bot pushed a commit that referenced this issue Sep 22, 2022
@AlpinYukseloglu
[stableswap]: Switch two-asset CFMM solver to use BigDec binary sea…
9b9c9f5 
…rch (#2816)

Progress towards: #2794 

## What is the purpose of the change

This PR replaces our stableswap two-asset CFMM solver to use the `BigDec` binary search implementation in #2802 

Note: most of the diff is tests merged from #2697 and the core binary search logic from #2802, both of which had to be merged into this branch

## Brief Changelog

- Replace binary search solver logic with our `BigDec` binary search implementation

## Testing and Verifying

- All two-asset CFMM test cases were set up to test this implementation in `amm_test.go`

## 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 documented)
Repository owner moved this from Needs Review 🔍 to Done ✅ in Osmosis Chain Development Sep 26, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@AlpinYukseloglu AlpinYukseloglu

Labels
C:stableswap
Projects
Osmosis Chain Development
Archived in project
Milestone
No milestone
Development

No branches or pull requests
1 participant
@AlpinYukseloglu