Re: Fun with Unbounded Rational Numbers

[antispam@math.uni.wroc.pl]

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

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