Complexity of numerical operations

Question

I have written a program which contains a while loop: while k < sqrt(n), so clearly my program evaluates $\sqrt{n}$ at each iteration of the while loop. (Note that $n$ and $k$ can both change throughout the loop, although I do not think that this is relevant to the question.)

I am required to calculate the number of arithmetic operations used by my program in terms of the initial value of $n$ (in terms of the number $n$, not the number of digits of $n$) when it is run, where an arithmetic operation is defined as the addition, subtraction, multiplication or division of any two numbers.

My question is, how many arithmetic operations does $\sqrt{n}$ use? Is it a fixed amount or does it change with $n$ (and if so to what extent)?

Answer 1

If you have a look at this wikipedia page then you will see that there are over tens of algorithms for calculating the square root of a number.

Let's consider the Babylonian method for calculating square roots. This is very similar to Newton's iterative method for finding roots and therefore an approximation algorithm. The pseudocode is as follows:

1. Start with an arbitrary positive start value x. 
The closer this value is to the actual root, the better the convergence is.

2. Initialize y = 1.
This variable will hold the value for the previous iteration of the root.

3. Initialize e = some arbitrary small value.
This will determine the accuracy of our root.

4. Do following until (x - y) > e :
  a) Set y = (n/x)
  a) Set x = (y + x) / 2

This answer gives a good look into how the running time complexity of the above method can be obtained. The TLDR version is $O(log(log(n))$ for $\sqrt(n)$.

A small thing to note is that if n can change throughout the loop, then the square root will be calculated every time the loop is run. However if n does not change at all, it is treated as a loop invariant and the compiler takes steps to optimize the performance internally. In short, the calculation of the square root is taken outside the loop body.

Finally, since there are multiple algorithms for calculating the root of a number there is no single solution to the question:

how many arithmetic operations does (√n) use?

As for the second question, ie:

Is it a fixed amount or does it change with n (and if so to what extent)?

You can clearly see that its not a fixed amount, and the number of operations depend on the value of n itself, the initial root chosen and the level of accuracy preferred.

Some related additional reading for iterative algorithms: Gradient Descent.