Re: Fun with Unbounded Rational Numbers

["Jeffrey R. Carter" <spam.jrcarter.not@spam.not.acm.org>]

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