Anomaly in mpn_sqrtrem and mpn_rootrem

[Niels Möller]

bodrato at mail.dm.unipi.it writes:

> An example:
> B=10
> A=9876 (4 digits)

I'm thinking of a slightly different arrangement.

At the top-level sqrtrem, since we have 4 digits, we have to use the top
3 to get an accurate square root approximation. So we'll call a function
to compute sqrt(987 * B^1). With three digits input and 2 digits output,
so this is the function call I've denoted by sqrt_nm1(3, 987), for lack
of a better name.

Next, sqrt_nm1 will split off the top two digits, and recursively
compute 

  H = sqrt_nm1(2, 98) 

This is handled as the base base, returning floor (sqrt(98)) = 9. So we
get H = 9.

Since we had an odd number of digits (3), the residual is

  E = 987 - B H^2 = 987 - 810 = 177.

We then return

  X = B H + floor (E / 2H) = 90 + floor(177 / 18) = 99

So this is the value returned to the top-level sqrtrem,

  sqrt_nm1(3, 987)   --->   99

Finally, the top-level may need an adjustment taking the final digit
into account. In this example, no adjustment is needed. One case where
it is needed is if the top-level input happens to be a square, and with
a non-zero least significant digit. E.g, 8836, where sqrt_nm1(3, 883)
returns 93, one off from the correct square root 94.

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

I hope I've made it a little bit clearer. (I'm actually working on an
implementation, so we can play more with it).

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.