serie of sqrt
l.couraud at free.fr
Wed Mar 17 00:08:20 CET 2004
----- 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
> > 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
or more complex
More information about the gmp-devel