Content deleted Content added
→Complexity ?: new section |
→Complexity ?: like division |
||
Line 217:
I'm disappointed but almost even more surprised that the word "complexity" does not occur a single time on that page... On [[Computational_complexity_of_mathematical_operations]] it is written that the complexity of sqrt is that of multiplication, but that's IMO far from obvious. Some details here would have been nice. — [[User:MFH|MFH]]:[[User talk:MFH|Talk]] 19:34, 11 November 2012 (UTC)
:I compare [[Methods of computing square roots#Iterative methods for reciprocal square roots]] with [[Division algorithm#Newton–Raphson division]]:
::<math>x_{n+1} = \frac{x_n}{2} \cdot (3 - S \cdot x_n^2) \,</math>
::<math>X_{i+1} = X_i(2-DX_i) \,</math>
:and conclude that the complexity of extracting a square-root is only slightly greater than the complexity of division. But division is significantly harder than multiplication since it requires repeated multiplication of the order of the logarithm of the number of digits times. [[User:JRSpriggs|JRSpriggs]] ([[User talk:JRSpriggs|talk]]) 07:16, 12 November 2012 (UTC)
| |||