| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 154 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 146 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 135 |
| 9 | maroonrk | 133 |
| 10 | cry | 130 |
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
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.
Thank you Yes I am aware of the log n method but does the built in sqrt() use this algorithm?
.
Please do not post links to offensive sites such as GeeksForGeeks, many of those who visit CodeForces are underage...
"offensive" as in?
he is joking, because gfg have many wrong, inaccurate articles.
They probably use Newton's Method.
Thanks
sqrt is directly compiled to
sqrtsdinstruction 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 requiressqrtto 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).