0
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I forgot to mention that n will always be an integer. My thinking on this was that If we think about how a number is stored in a computer we have the sign, the exponent and the mantissa. And to find the square root, we can simply divide the exponent by 2. This is clearly just a division of 2 numbers, does a computer optimise itself and do this? $\endgroup$ – KingJ Apr 20 '18 at 11:56
  • $\begingroup$ Obviously slightly more complicated than I've written above, but that method with say a lookup table for the mantissa would be very efficient? $\endgroup$ – KingJ Apr 20 '18 at 12:30
  • $\begingroup$ I don't think that's going to work since the IEEE representation with mantissa and exponent only applies to floating point numbers. Here you are talking about integers. $\endgroup$ – Sagnik Apr 21 '18 at 3:49
  • $\begingroup$ Have a look at this: physics.utah.edu/~detar/phys6720/handouts/IEEE.txt $\endgroup$ – Sagnik Apr 21 '18 at 3:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.