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!newsfeed.fsmpi.rwth-aachen.de!newsfeed.straub-nv.de!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: Sun, 9 Apr 2017 19:25:05 +0000 (UTC)
Organization: Politechnika Wroclawska
Message-ID: <oce1qh$let$1@z-news.wcss.wroc.pl>
References: <ocaec1$a0p$1@dont-email.me> <ocbvbn$h8r$1@z-news.wcss.wroc.pl>
 <occs8h$6f4$1@dont-email.me>
NNTP-Posting-Host: hera.math.uni.wroc.pl
X-Trace: z-news.wcss.wroc.pl 1491765905 21981 156.17.86.1 (9 Apr 2017 19:25:05
 GMT)
X-Complaints-To: abuse@news.pwr.wroc.pl
NNTP-Posting-Date: Sun, 9 Apr 2017 19:25:05 +0000 (UTC)
Cancel-Lock: sha1:IPtkqA2LyiKaOyupDITZW0jtXlg=
User-Agent: tin/2.2.1-20140504 ("Tober an Righ") (UNIX) (Linux/4.9.5 (x86_64))
Xref: news.eternal-september.org comp.lang.ada:46556
Date: 2017-04-09T19:25:05+00:00
List-Id: <comp.lang.ada>

Jeffrey R. Carter <spam.jrcarter.not@spam.not.acm.org> 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.

-- 
                              Waldek Hebisch