Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

ar88lo's blog

Is sqrt calculated in constant time in c++?(how?)
By ar88lo, history, 3 years ago, In English

Hi I was quite sure about this matter until I came across a comment in a old blog that suggested other wise I searched the internet but I didn't find anywhere mentioning anything about logarithmic runtime(and no source said anything about constant time) but I'm just checking

Thanks

  • Vote: I like it
  • -14
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it -10 Vote: I do not like it

I guess you can think of binary searching the value of $$$\sqrt{n}$$$, you know that it must range from 1 to $$$n$$$, so it takes $$$log(n)$$$ runtime. Please correct me if I am wrong.

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

    Thank you Yes I am aware of the log n method but does the built in sqrt() use this algorithm?

    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it -22 Vote: I do not like it

.

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

    Please do not post links to offensive sites such as GeeksForGeeks, many of those who visit CodeForces are underage...

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

      "offensive" as in?

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

      he is joking, because gfg have many wrong, inaccurate articles.

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

They probably use Newton's Method.

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +14 Vote: I do not like it

sqrt is directly compiled to sqrtsd instruction on x86 starting with -O1. We can only speculate how it works in hardware. It certainly does not use Newton-Raphson method because IEEE-754 requires sqrt to have perfect precision (<= 0.5 ulp). It probably uses a method similar to long division (which is also a speculation, but it makes sense because div and sqrt are implemented in the same hardware unit).

→ Reply