??? 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. |
Topic | Author | Date |
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 |