From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=unavailable autolearn_force=no version=3.4.4 Path: eternal-september.org!reader01.eternal-september.org!reader02.eternal-september.org!news.eternal-september.org!news.eternal-september.org!feeder.eternal-september.org!weretis.net!feeder4.news.weretis.net!ecngs!feeder2.ecngs.de!81.171.118.63.MISMATCH!peer03.fr7!futter-mich.highwinds-media.com!news.highwinds-media.com!newsfeed.neostrada.pl!unt-exc-02.news.neostrada.pl!newsfeed.pionier.net.pl!pwr.wroc.pl!news.wcss.wroc.pl!not-for-mail From: antispam@math.uni.wroc.pl Newsgroups: comp.lang.ada Subject: Re: Fun with Unbounded Rational Numbers Date: Tue, 11 Apr 2017 21:39:42 +0000 (UTC) Organization: Politechnika Wroclawska Message-ID: References: NNTP-Posting-Host: hera.math.uni.wroc.pl X-Trace: z-news.wcss.wroc.pl 1491946782 7467 156.17.86.1 (11 Apr 2017 21:39:42 GMT) X-Complaints-To: abuse@news.pwr.wroc.pl NNTP-Posting-Date: Tue, 11 Apr 2017 21:39:42 +0000 (UTC) Cancel-Lock: sha1:ntqGtjrRMiNVTaKW5CGtnON4MUw= User-Agent: tin/2.2.1-20140504 ("Tober an Righ") (UNIX) (Linux/4.9.5 (x86_64)) X-Received-Bytes: 3395 X-Received-Body-CRC: 1303114676 Xref: news.eternal-september.org comp.lang.ada:46578 Date: 2017-04-11T21:39:42+00:00 List-Id: Jeffrey R. Carter wrote: > On 04/09/2017 09:25 PM, antispam@math.uni.wroc.pl wrote: > > Jeffrey R. Carter wrote: > >> On 04/09/2017 02:30 AM, antispam@math.uni.wroc.pl wrote: > >>> > >>> newton(y : Fraction(Integer), eps : Fraction(Integer)) : Fraction(Integer) == > >>> x : Fraction(Integer) := 1 > >>> while abs(y - x^2) >= eps repeat > >>> x := (x + y/x)/2 > >>> x > >> > >> Maybe I'm missing something, but this doesn't look like Newton's method to me. > >> > > > > We are sloving equation f(x) - y = 0 where f(x) = x^2. Newton says: > > > > x_{n+1} = x_{n} - (f(x_n) - y)/f'(x_n) > > > > we have > > > > f'(x) = 2x > > > > so > > > > x_{n+1} = x_{n} - (x_n^2 - y)/(2*(x_n)) = > > x_{n} - x_n^2/(2*(x_n)) + y/(2*(x_n)) = > > x_{n} - x_n/2 + y/(2*(x_n)) = > > x_{n}/2 + y/(2*(x_n)) = (x_{n} + y/x_n)/2 > > > > So indeed given the same initial approximation the formula produces > > exactly the same sequence of numbers as direct use of Newton formula, > > but is slightly cheaper to compute. > > As I learned it, Newton's method is to iteratively improve an estimate of the > (positive) root of > > Y = X**2 - R > > At each step, the next estimate is the root of the line through (X, Y) with slope > > M = Y' = 2 * X > > which works out to > > X - Y/M > > Substituting in the definitions of Y and M, it's easy to show this is the same > as your version. I guess I'd never seen it simplified further. > > As to being cheaper to calculate, is that true? For rational math, division is > multiplication and subtraction is addition, so both have 2 multiplications and > an addition. > For rational math key factor is size of numbers. Y has size approximatly twice size of X plus size of R. M is about the same as X, so Y/M is approximatly 3 times size of X plus size of R before canceling common factors. Without canceling common factors X - Y/M would be approximatly 4 times size of X plus size of R, that is twice as large (assuming small R) as the version I gave. And without canceling common factors the difference in size will accumulate leading to much worse behaviour. With canceling common factors the most expensive part is computing GCD-s and your version leads to larger GCD-s. But the difference will be moderate. -- Waldek Hebisch