Email: Password: Remember Me | Create Account (Free)

Back to Subject List

Old thread has been locked -- no new posts accepted in this thread
???
10/04/08 16:08
Modified:
  10/04/08 16:16

Read: times


 
Msg Score: +2
 +2 Good Answer/Helpful
#158839 - Algorithm is important
Responding to: ???'s previous message
Now that is not a good algorithm.

A pocket calculator using this algorithm would die if you enter a really large number and requests the square root.

Way faster is to do something like:
double sqrt(double n) {
    double x,newx;
    x = n;
    for (unsigned i = 0; i < 10; i++) {
        newx = 0.5*(x + n/x);
        printf("%u\t%g\t%g\n",i,x,newx);
        x = newx;
    }
    return x;
}

You will about double the number of correct value digits for each iteration.

You normally don't run a fixed number of iterations, but keep track of the change between two steps.

If the above is run with input number 2, it will produce:
0       2       1.5
1       1.5     1.41667
2       1.41667 1.41422
3       1.41422 1.41421
4       1.41421 1.41421
5       1.41421 1.41421
6       1.41421 1.41421
7       1.41421 1.41421
8       1.41421 1.41421
9       1.41421 1.41421

When designing an algorithm, it is important to think about the converge. Both that it does converge, but also how fast it will converge. Some problems are easy - some are hard.

But having an algorithm that steps a fixed step at a time results in a linear - proportional - time to get to the end. That may be the best possible if you are trying to find a minimum in a table of entries - you have to test every row or column in the table.

But sqrt and sqr are nice functions. A better way to design from scratch is to have an algorithm that varies the step sizes.

Test 1. If too little then test 2. If to little then test 4. If to little then test 8. Double the step for each iteration until the solution is bracketed, i.e. you have one attempt below and one above. Then start halving the interval and work backwards again. This approach are always safe when the equation you are processing doesn't have any bumps you may step past and miss by taking too large steps. But the square of (n+eps) (where n and eps are positive) is always larger than the square of n, so a too large step can never diverge.

List of 11 messages in thread
TopicAuthorDate
code library for 24 bit sqare root in asm            01/01/70 00:00      
   So, what have you tried ?            01/01/70 00:00      
   Is the " subject problem" homework?            01/01/70 00:00      
      code library for 24 bit sqare root in asm            01/01/70 00:00      
         Algorithm is important            01/01/70 00:00      
            thinking            01/01/70 00:00      
            Integer?            01/01/70 00:00      
               Fixed-point or integer            01/01/70 00:00      
                  Issues with Newton-approximation            01/01/70 00:00      
               Excellent link            01/01/70 00:00      
   fixed point or integer method of Per Westermark            01/01/70 00:00      

Back to Subject List