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.

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

ApproxRoot Infinite Looping #7038

Closed
4 tasks
migueldingli1997 opened this issue Aug 13, 2020 · 8 comments · Fixed by #7140
Closed
4 tasks

ApproxRoot Infinite Looping #7038

migueldingli1997 opened this issue Aug 13, 2020 · 8 comments · Fixed by #7140
Assignees

Comments

@migueldingli1997
Copy link
Contributor

Summary of Bug

Infinite loop when supplying small values to the Dec.ApproxRoot() function, most likely because the SmallestDec boundary is never satisfied. Example input: ApproxRoot(NewDecWithPrec(10000000000, 18), 3)

Version

Commit: 6a7cf4442e340b1878b28552778e42d3c6285624 (master as of writing)

Steps to Reproduce

Add the following test case to TestApproxRoot function in types/decimal_test.go:

  • {NewDecWithPrec(10000000000, 18), 3, MustNewDecFromStr("0")},

For Admin Use

  • Not duplicate issue
  • Appropriate labels applied
  • Appropriate contributors tagged
  • Contributor assigned/self-assigned
@alexanderbez
Copy link
Contributor

/cc @sunnya97 :(

@alessio
Copy link
Contributor

alessio commented Aug 18, 2020

I'd propose to remove the feature in master and reintroduce it when we have a fix.
For what concerns the Launchpad Release Series, we must communicate this ASAP (and maybe even remove it)

@alexanderbez
Copy link
Contributor

Fine by me -- feel free to remove entirely.

@sunnya97
Copy link
Member

@karzak Are you using this function?

@karzak
Copy link
Contributor

karzak commented Aug 19, 2020

No - this doesn't have an impact on Kava.

@migueldingli1997
Copy link
Contributor Author

migueldingli1997 commented Aug 20, 2020

I understand why it would be removed, but is there the possibility of restricting it to a known range of valid inputs or a larger error tolerance rather than removing it completely? Or maybe an alternative approach can be found? It is currently used by the bonds module. In any case, I'm happy to see the bug get squished.

@alessio
Copy link
Contributor

alessio commented Aug 20, 2020

As discussed with @migueldingli1997, he'll take a stab at this

@migueldingli1997
Copy link
Contributor Author

I'm thinking that with any implementation with no hard limit, there might always be the possibility that we get an infinite loop. So in my opinion the simplest solution without messing too much with the current code is to add an extra 'maximum number of iterations' argument which puts a hard limit on the looping. From my experimentation, it seems typically the number of iterations required is in the 10's, so maybe a hard limit that could be used would be 100. Will open a PR with this solution.

alessio added a commit that referenced this issue Aug 29, 2020
Added a maximum number of iterations (100) to ApproxRoot
(and ApproxSqrt) to serve as a hard limit on the number of
iterations that the algorithm performs. If the answer converges
before the maximum iterations, it returns immediately. Otherwise,
if the answer never converges enough to satisfy the primary loop
condition, the looping stops after a hundred iterations.

Closes: #7038

Co-authored-by: Alessio Treglia <[email protected]>
alessio pushed a commit that referenced this issue Aug 29, 2020
Added a maximum number of iterations (100) to ApproxRoot
(and ApproxSqrt) to serve as a hard limit on the number of
iterations that the algorithm performs. If the answer converges
before the maximum iterations, it returns immediately. Otherwise,
if the answer never converges enough to satisfy the primary loop
condition, the looping stops after a hundred iterations.

Closes: #7038
alessio pushed a commit that referenced this issue Aug 31, 2020
Added a maximum number of iterations (100) to ApproxRoot
(and ApproxSqrt) to serve as a hard limit on the number of
iterations that the algorithm performs. If the answer converges
before the maximum iterations, it returns immediately. Otherwise,
if the answer never converges enough to satisfy the primary loop
condition, the looping stops after a hundred iterations.

Closes: #7038

Co-authored-by: Miguel Dingli <[email protected]>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

Successfully merging a pull request may close this issue.

5 participants