Блог пользователя ar88lo

Is sqrt calculated in constant time in c++?(how?)
Автор ar88lo, история, 3 года назад, По-английски

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

  • Проголосовать: нравится
  • -14
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

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

    → Ответить
»
3 года назад, # |
← Rev. 2   Проголосовать: нравится -22 Проголосовать: не нравится

.

→ Ответить
»
3 года назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

They probably use Newton's Method.

→ Ответить
»
3 года назад, # |
← Rev. 2   Проголосовать: нравится +14 Проголосовать: не нравится

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).

→ Ответить