Square Root Process Similar to Long Division
|
11-06-2022, 04:33 PM
Post: #7
|
|||
|
|||
RE: Square Root Process Similar to Long Division
(09-18-2021 01:07 PM)Albert Chan Wrote: Newton's method converge fast, but required expensive mul/div. We can do as Newton did and use this equation instead: \( \begin{align} \frac{1}{x^2} = d \end{align} \) Using Newton's method we get the following recurrence: \( \begin{align} x \leftarrow x + \frac{x(1 - d \cdot x^2)}{2} \end{align} \) So we can get rid of the expensive division and only have to divide by 2. To get \(\sqrt{d}\) we have to multiply the final result \(x\) by \(d\). Program This is the corresponding Python program: Code: def newton(d, x, n): Examples d = Decimal('.9996') x = Decimal('1') newton(d, x, 7) 0.9996 0.99979992 0.99979997999599359936 0.99979997999599899971991597354766255640239090891735007232 0.9997999799959989997199159735914171390272639623863827366463080538247902204151860911590260475681681352 0.9997999799959989997199159735914171390272639623863827366491803235872148569016030640762583498945948583 0.9997999799959989997199159735914171390272639623863827366491803235872148569016030640762583498945948583 d = Decimal('12345') x = Decimal('0.009') newton(d, x, 7) 111.105 111.1080553875 111.1080555135405110305346994140625 111.1080555135405112450044387430752408689311675830734154751136313016974218865863978862762451171875 111.1080555135405112450044387430752414899113774596977299764856731617825851115519126275283305922167024 111.1080555135405112450044387430752414899113774596977299764856731617825903175167629180920706522637384 111.1080555135405112450044387430752414899113774596977299764856731617825903175167629180920706522637384 Depending on the use case only a few iterations might be needed. Still the multiplications might get tedious after a while. |
|||
« Next Oldest | Next Newest »
|
Messages In This Thread |
Square Root Process Similar to Long Division - jeejohn - 09-17-2021, 11:00 PM
RE: Square Root Process Similar to Long Division - Albert Chan - 09-17-2021, 11:58 PM
RE: Square Root Process Similar to Long Division - Albert Chan - 09-18-2021, 01:51 AM
RE: Square Root Process Similar to Long Division - Albert Chan - 09-18-2021, 12:46 PM
RE: Square Root Process Similar to Long Division - Albert Chan - 09-18-2021, 01:07 PM
RE: Square Root Process Similar to Long Division - jeejohn - 09-18-2021, 08:55 PM
RE: Square Root Process Similar to Long Division - Thomas Klemm - 11-06-2022 04:33 PM
RE: Square Root Process Similar to Long Division - Thomas Okken - 11-06-2022, 07:25 PM
|
User(s) browsing this thread: 1 Guest(s)