3 ms·
Much faster algorithm, calling your input value X: 1. Move the decimal point 2N digits to the left, so that your value X is of the form a.bcdef... or ab.cdef..
by cperciva 18y ago
Much faster algorithm, calling your input value X:
1. Move the decimal point 2N digits to the left, so that your value X is of the form a.bcdef... or ab.cdef... Remember the value N.
2. If X now has one digit before the decimal place, set Y = 5. Otherwise, set Y = 2.
3. Compute Y = Y * (300 - X * Y * Y) / 200 to as many decimal places as you want. Feel free to start by computing only a few decimal places.
4. Repeat step 2 until you're computing Y to the number of decimal places you want in your answer and it's not changing.
5. Compute Y = X * Y.
6. Move the decimal point in Y to the right by N-1 places.
- jpwagner 18y agoI'm sorry, but this is totally unclear (to me at least). For example what are you computing (in part 3) if you know what X and Y are? What is N? What is "the number of decimal places you want"? Can you explain in another way? Do you have an example? Why does this work?
- jibiki 18y agoPart 3 makes perfect sense to me, it's an "x = x+1" style line. N is (((the number of digits of X), divided by 2), rounded down.) Edit: hmm, maybe I've got it wrong, the convergence is very slow. Anyways, here's how it works out for me: X = 105362 X = 10.5362 so N = 2 (half the number of digits to the right of the decimal point...) Y = 2 Y = 2*(300-10.5362*2*2) = 2.578552 Y = 2.578552*(300-10.5362*2.578552*2.578552) = 2.9646326 Y = 2.9646326*(300-10.5362*2.9646326*2.9646326) = 3.0742773 It should converge to around 3.24, at which point you would shift the decimal point back 2 digits to get 324.
- jpwagner 18y agoI guess I'm confused by the fact that you are repeating step 2 which reassigns Y... Clear on N thanks. An example would make this easier...
- jibiki 18y agoYeah, it should read "repeat step three". Frequently, if you want to find x satisfying f(x) = x you can just let x be the limit of the sequence t, f(t), f(f(t)), f(f(f(t))) where t is some arbitrary number. In this case, we have: f(Y) = Y*(300-XYY)/200 If f(Y) = Y, then: Y = Y*(300-XYY)/200 1 = (300-XYY)/200 200 = 300 - XYY 100 = XYY So it looks like the algorithm calculates an inverse square root instead, and then multiplies it by the original number (step 5.)
- cperciva 18y agoYeah, it should read "repeat step three". Oops, quite right. So it looks like the algorithm calculates an inverse square root instead, and then multiplies it by the original number (step 5.) Exactly. The nice thing about this method is that it converges nicely even if you make errors (arithmetical or rounding) along the way -- so you can start by working with only a few digits and only use full precision right at the end. You could compute square roots using a direct NR iteration (Y := (Y + X/Y) / 2), but that requires that you perform a division at each step -- most people find multiplications to be easier and faster.
- huhtenberg 18y agoNice, but it is hardly fit for computing a root by hand.