Issue #21217 has been updated by mame (Yusuke Endoh). Thank you. I think it's most likely a Ruby bug, but I can't proceed until I identify the input that causes it. I still believe Ruby is the cause, but I can't rule out a Python bug. (AtCoder's answer might have been generated with Python.) Also, blindly applying linear correction is risky. If Ruby's result is far off due to the bug, the correction could take a huge amount of time. ---------------------------------------- Bug #21217: Integer.sqrt produces wrong results even on input <= 1e18 https://bugs.ruby-lang.org/issues/21217#change-112569 * 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/

Issue #21217 has been updated by mame (Yusuke Endoh). https://github.com/ruby/ruby/pull/13076 ---------------------------------------- Bug #21217: Integer.sqrt produces wrong results even on input <= 1e18 https://bugs.ruby-lang.org/issues/21217#change-112571 * 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/

Issue #21217 has been updated by hjroh0315 (Matthew Roh). mame (Yusuke Endoh) wrote in #note-3:

https://github.com/ruby/ruby/pull/13076

Thanks for the quick resolution! ---------------------------------------- Bug #21217: Integer.sqrt produces wrong results even on input <= 1e18 https://bugs.ruby-lang.org/issues/21217#change-112573 * 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/

Issue #21217 has been updated by k0kubun (Takashi Kokubun). Backport changed from 3.2: REQUIRED, 3.3: DONE, 3.4: REQUIRED to 3.2: REQUIRED, 3.3: DONE, 3.4: DONE ruby_3_4 commit:9abd48df705c37f69ec9fd954f84cbbbd65db624 merged revision(s) commit:3a7b9ca93b91dcc086b9ac8b9957e59268f9493b. ---------------------------------------- Bug #21217: Integer.sqrt produces wrong results even on input <= 1e18 https://bugs.ruby-lang.org/issues/21217#change-112704 * Author: hjroh0315 (Matthew Roh) * Status: Closed * ruby -v: 3.2.2 * Backport: 3.2: REQUIRED, 3.3: DONE, 3.4: DONE ---------------------------------------- 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/