[ruby-core:121546] [Ruby Bug#21217] Integer.sqrt produces wrong results even on input <= 1e18

Issue #21217 has been updated by hjroh0315 (Matthew Roh).


Thanks for the quick resolution!

----------------------------------------
Bug #21217: Integer.sqrt produces wrong results even on input <= 1e18
https://bugs.ruby-lang.org/issues/21217#change-112572

* Author: hjroh0315 (Matthew Roh)
* Status: Open
* ruby -v: 3.2.2
* Backport: 3.2: UNKNOWN, 3.3: UNKNOWN, 3.4: UNKNOWN
----------------------------------------
Hello, I have been so far using Ruby in various online judge platforms that support it, while recently I discovered a very intriguing issue regarding `Integer.sqrt`.

Please refer to the two following verdicts on this recent problem that requires the usage of such a function:

- [Python 3.11.4](https://atcoder.jp/contests/abc400/submissions/64536518)
- [Ruby 3.2.2](https://atcoder.jp/contests/abc400/submissions/64577995)

The input constraints of the problem guarantees that n <= 1e18, and judging from the fact that [implementing the same functionality using binary search](https://atcoder.jp/contests/abc400/submissions/64578791) gets a correct verdict, it is quite apparent that `Integer.sqrt` is producing wrong results even on input <= 1e18.

While I have not been able to reproduce this issue locally, it is not hard to imagine that the latest version of Ruby might still have the same issue considering there has been no similar bugfix request in the last 2~3 years.

I believe an easy way to fix this bug is to simply adjust the result to the correct one using a linear search (`while(x*x<=n)x++; while(x*x>n)x--;`) in the end.

Thank you for reading the bugfix request, and for your continued effort on maintaining the language.



-- 
https://bugs.ruby-lang.org/
 ______________________________________________
 ruby-core mailing list -- [e-mail]
 To unsubscribe send an email to [e-mail]
 ruby-core info -- https://ml.ruby-lang.org/mailman3/lists/ruby-core.ml.ruby-lang.org/