Say I make a program that calculates all possible (integral) factors of a certain number that has been input.
Is it theoretically more efficient to check with all integers up to the square root of the number or till half of the number.
Calculating the square root will take more time and power but will result in fewer divisions and vice-versa for the other option.
2
A square root isn’t that long to compute for modern CPUs. It is better to compute the square root than to continue running your loop up to n/2. Except maybe for very small n’s.
There are ways to reduce the cost of square roots: Precompute the square root:
int max = (int)Math.sqrt(n);
for(int k=2 ; k <= max ; k++)...
or use an integer multiplication in your test
for(int k=2 ; k*k <= n ; k++)...
3
Before we start,
- Know what the use case is for
- Learn how to measure performance scientifically, like a pro. Takes years to learn but there is no recurring cost applying the knowledge.
Firstly, optimize for use case.
- For an interview, just use the standard library
sqrt, floored to integer, take out factor of 2 as a special case, so that you only need to loop over odd integer factors beginning with 3. - For absolute awesomeness, implement Sieve of Eratosthenes –
- But don’t try to impress with an interviewer with this (aside from just name-dropping) – you don’t want to risk timeouts or typos proportional to amount of code.
If for some reason one has to implement square-roots on CPUs without native support,
- Your standard library may have it; if so, use it.
- Otherwise, the first two often-quoted strategies are:
- Method of bisection, or binary search, or bit-guessing. Works 1 bit of root estimate at a time.
- Given
r^2 <= floor(n/4) < (r+1)^2, test(2*r+1)^2againstn - Make use of the identity
(2*r+1)^2 == (4*r^2 + 4*r + 1)
- Given
- Newton-Raphson method.
- The choice comes down to whether the CPU has good division performance or not.
- Method of bisection only requires fast bit shifts, addition, subtraction and comparisons.
- Newton-Raphson requires division (integer or float).
- Method of bisection, or binary search, or bit-guessing. Works 1 bit of root estimate at a time.
- If you are synthesizing hardware, you can use a table lookup for the highest 10 bits or so, and then continue with either bisection or Newton-Raphson method.
All of the information above can be gathered by searching on Google, Wikipedia, Stackoverflow, and other hobbyist sites.
- https://stackoverflow.com/questions/1100090/looking-for-an-efficient-integer-square-root-algorithm-for-arm-thumb2
- http://www.finesse.demon.co.uk/steven/sqrt.html
Nowadays processors ‘enjoy’ working on float numbers and provides support for square roots and powers. I think engeeners which implemented Math.sqrt(n) method, took care of efficiency better than multiplying in a loop.