Anomaly in mpn_sqrtrem and mpn_rootrem

[bodrato at mail.dm.unipi.it]

Ciao,

Il Mer, 8 Luglio 2015 8:31 am, Niels Möller ha scritto:
> bodrato at mail.dm.unipi.it writes:
>
>> If H=floor(sqrt(A/B^2n)), then the residual we need to compute the lower
>> half of the square root is floor(A/B^2n)-H^2 .
>
> I don't follow you here. Consider a simple case: A of size 2n, and we
> try to compute an approximation of sqrt(B^{2n-2} A).
>
> Then first compute high half as
>
>   H \approx sqrt(B^{n-2} floor (B^{-n} A))
>
> And the residual is
>
>   E = H^2 - A (appr. n limbs, due to cancellation)

E is approximatively 3n/2 limbs.

An example:
B=10
A=9876 (4 digits)
To compute the high half, we consider A'=98 (2 digits),
we compute H'=sqrt(98)=9 (1 digit).
(A'=H'^2+17, 17 <= 2*H', this result is exact, the first digit will not be
changed by any following step...)

Then H=90 (2 digits)
E=A - H^2 = 9876-90^2 = 1776 (slightly more than 3 digits...)

But we do not need all of E, we can simply use
E' = (A'-H'^2)*B + second_digit_of(A) = (98-9^2)*10 +... = 177
We computed (98-9^2), the remainder of the high half...
Then 177/9/2 = 9 is the second digit.

... but maybe I did not understand the algorithm you proposed.

Best regards,
m

-- 
http://bodrato.it/