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.
-
It really should vary on different CPUs. Some very lowend CPUs (e.g. $1 microcontrollers) might not even have any FPU (or a cheap FPU unable to compute square roots)– Basile StarynkevitchSep 13, 2014 at 19:58
-
@BasileStarynkevitch Software emulation is slow, but not that much slower (for n = 1000 it would have to be 15x slower than an integer division which likely won't have hardware support either) and hand-rolling a square root for integers is quite feasible (for anyone who had enough calculus to know the bisection method) and rather efficient (about k iterations for n < 2^k with each iteration only requiring a few additions and a single multiplication).– user7043Sep 13, 2014 at 23:17
Add a comment
|
3 Answers
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++)...
-
2The pre-computed square root is more efficient than the multiplication that must be done each time around the loop. Sep 13, 2014 at 18:37
-
Right. I did some extra timings. It also seems that a loop up to a fixed value is faster than a loop that stops on a boolean expression. This even if the loop runs a single time. It seems the flow is better optimized in the first case. Sep 21, 2014 at 0:07
-
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.
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.
