serie of sqrt

laurent couraud l.couraud at
Wed Mar 17 00:08:20 CET 2004

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

> "laurent couraud" <l.couraud at> writes:
> >
> > Because the entire part of the square root of a + n*h and the entire
> >  of the square root of a + (n + 1)*h can be equal or very near, if we
> > the initial value in the Newton algorithm we probably gain the square
> > 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

More information about the gmp-devel mailing list