Anomaly in mpn_sqrtrem and mpn_rootrem
nisse at lysator.liu.se
Wed Jul 8 21:43:35 UTC 2015
bodrato at mail.dm.unipi.it writes:
> An example:
> 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
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).
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.
More information about the gmp-devel