serie of sqrt

[laurent couraud]

----- Original Message ----- 
From: "Kevin Ryde" <user42 at zip.com.au>
To: "laurent couraud" <l.couraud at free.fr>
Cc: <gmp-devel at swox.com>
Sent: Tuesday, March 16, 2004 11:20 PM
Subject: Re: serie of sqrt


> "laurent couraud" <l.couraud at free.fr> writes:
> >
> > Because the entire part of the square root of a + n*h and the entire
part
> >  of the square root of a + (n + 1)*h can be equal or very near, if we
inject
> > the initial value in the Newton algorithm we probably gain the square
root
> > with a very small number of iteration.
>
> I'm not sure I understand.
>
> If you calculate the square root (s) and remainder (r) using
> mpz_sqrtrem of some value x, then I think from that you can know where
> nearby perfect squares are located using some additions.  x-r is the
> next lower one (ie. s^2 of course), and the next higher one would be
> x-r+2*s+1, then x-r+4*s+4, etc.
>

Yes, it's true, but only if the difference is the affine function.

If we search a square that verify:

a + n1*h^2 + n2*h +n3 = b^2

where a, n1, n2, n3 are know and where we search an integer h that verify
this equation

or more complex