paul zimmermann <paul.zimmerm...@inria.fr> writes:
> In the second case (lines 267-276) this is less obvious since you use an
> approximate division (divappr), and I don't know what is the maximal allowed
> difference between divappr and div. If divappr always return a quotient
> less or equal to the true quotient, then qh cannot be zero in this case.
> But if qh can be larger than the true quotient, even by one bit, then it
> is possible that qh is 1, in the case {new_np, new_nn} = 0111...111 and
> {new_dp, dn} = 1000...000.
You're right again... I thought we had more margin.
According to comments, quotient from sb and dc divappr is correct or
one too large, while quotient from mu divappr can be at most 4 too
large.
And the limit case, N = B^n/2 - 1, D = B^k/2 is
floor ((B^n/2 - 1) / (B^k/2)) = floor(B^{n-k} - B^{-k}/2)
= B^{n-k} - 1
So even we only a single unit of error, we could get qh == 1.
I wonder what actual error can be produced by the divappr functions in
the corner cases that error could spill over into qh?
In the cy != 0 case, it looks like we we make a balanced divappr call,
(2qn+2) / (qn+1). Lets put k = qn+1. For divappr we then have
N <= B^{2k}/2 - 1,
D >= B^k/2, lets say D = B/2 + e, e >= 0
To have any possibility to get qh > 0 with from the approximation error,
we must have Q >= B^k - 4, where Q denotes the correct quotient. So
assume that is the case. Now,
D <= N/Q <= (B^{2k}/2 - 1) / (B^k - 4)
which implies
e <= N/Q - B^k/2 <= (2 B^k - 1) / (B^k - 4) < 3
So we need to consider only D = B^k/2 + {0, 1, 2}. Then, any inverse not
taking the very least significant D limb into account (including mu inverse)
must be *all* ones, right?
It would be good to either prove that qh > 0 can't happen, or add a test
that will exercise the code handling that case.
> beware that in the case cy <> 0, one divides {new_np, nn+1} by {new_dp, dn}
> thus filling {qp, nn-dn+1}.
Thanks for pointing this out. Now I understand better.
Regards,
/Niels
--
Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.
_______________________________________________
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel
