chromate00's blog

Quick Guide: Python's 'isqrt' function
By chromate00, 2 years ago, In English

On todays contest, at 1737B - Ela's Fitness and the Luxury Number, a lot of contestants were hacked or FSTed. This is due to the inaccurate nature of floating-point types. While I do think this happening on a B is not a good thing, but it happened anyways. So as we experienced a failure this time (myself a long time ago multiple times), we need to prepare for the next time it happens.

My solution to this was using Python's isqrt function. It receives a non-negative integer, and returns $$$\lfloor \sqrt{x} \rfloor$$$. It is guaranteed to return the accurate value, so this is the perfect tool for the job. I read this blog as well, and his points are valid. I still thought telling people about the isqrt function would be a great addition to the community as well. Shoutout to -is-this-fft- for writing that blog.

Including this time, there will be many situations where there is a better tool for the job. It is a good idea to actively look for them and use them to your advantage. This is the exact reason I am writing this blog, and other blogs such as the STL in CP series as well. I hope you try to do the same when learning and practicing CP as well.

p.s. I think there should be other languages with builtins serving the same functionality, or ways to do it in the language you use. Please suggest it in the comments section below! It would be a great addition to the topic.

UPD: I just found that this wikipedia page exists, please take a look if you're interested in other methods to do this!

  • Vote: I like it
  • +36
  • Vote: I do not like it

Comments Comments (9)
| Write comment?
»
2 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

I shall start the addition with one possible method in C++. You can use the sqrt function, and compensate its errors linearly. As it's represented with the closest possible floating-point value, the linear search will run a constant amount of times at maximum. Here is the code.

Code for C++
→ Reply
»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

for c++ use sqrtl() instead of sqrt() to get the right answer for big numbers

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    This works quite often, but doesn't ensure a 100% chance it will pass. It still relies on floating-point calculation, so it will be inaccurate in some way. That blog I linked in the middle of the blog explains it better than I can, shoutout to him :D

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can also code a Binary Search Square Root function that returns an integer. Its complexity is logarithmic and its accuracy is guaranteed

→ Reply
»
2 years ago, # |
  Vote: I like it +5 Vote: I do not like it

i apvtoed ser

→ Reply
»
2 years ago, # |
  Vote: I like it +2 Vote: I do not like it

i too apvtoed ser ^^ Botswanians stanting for eash atha

→ Reply