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!.POSTED!not-for-mail
From: "Jeffrey R. Carter" <spam.jrcarter.not@spam.not.acm.org>
Newsgroups: comp.lang.ada
Subject: Re: Fun with Unbounded Rational Numbers
Date: Mon, 10 Apr 2017 19:18:08 +0200
Organization: Also freenews.netfront.net; news.tornevall.net;
 news.eternal-september.org
Message-ID: <ocgeio$j21$1@dont-email.me>
References: <ocaec1$a0p$1@dont-email.me> <ocbvbn$h8r$1@z-news.wcss.wroc.pl>
 <occs8h$6f4$1@dont-email.me> <oce1qh$let$1@z-news.wcss.wroc.pl>
Mime-Version: 1.0
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Mon, 10 Apr 2017 17:15:04 -0000 (UTC)
Injection-Info: mx02.eternal-september.org;
 posting-host="8af9938be2f854ed69ca5489fadad29a";
	logging-data="19521"; mail-complaints-to="abuse@eternal-september.org";
	posting-account="U2FsdGVkX1/dyGCRrQxlHmW9+CyP4Ns2XYrBZp03iMc="
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101
 Thunderbird/45.8.0
In-Reply-To: <oce1qh$let$1@z-news.wcss.wroc.pl>
Cancel-Lock: sha1:voQ97ziH/d29qmzHKONlrH4kpOE=
Xref: news.eternal-september.org comp.lang.ada:46565
Date: 2017-04-10T19:18:08+02:00
List-Id: <comp.lang.ada>

On 04/09/2017 09:25 PM, antispam@math.uni.wroc.pl wrote:
> 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.

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.

-- 
Jeff Carter
"I didn't squawk about the steak, dear. I
merely said I didn't see that old horse
that used to be tethered outside here."
Never Give a Sucker an Even Break
103