Re: CLN, GMP inputs

[Hans Aberg]

At 10:06 +1000 2001/05/03, Kevin Ryde wrote:
>> I think that one should perhaps add mod and division a = q*b + r so that
>> abs(r) <= abs(b)/2.
>
>I guess that'd be mpz_ndiv, "n" for "nearest".  I'll put it on a todo
>list if you think it'd have important uses.

I cannot say how important it is, but I think if one should build a Z/nZ
class, then this variation should be given some thought.

>> I think this might be faster when working mod n (in Z/nZ).
>
>I'm not sure it'd help much, after all it only trims one bit from the
>size, and since all calculations are done in whole limbs that saving
>would rarely change the work done.
>
>If/when some modular arithmetic comes about it'll probably be done all
>unsigned internally, to suit the mpn routines.
>
>> For example, gcd converges faster.
>
>I've seen analyses of that sort of thing, but I'm a bit sceptical
>about it in practice.

For gcd, the idea is only that the absolute value is guranteed to halve in
each division, so one finds in in log_2 n time, then.

Then whether that is a speed advantage in practise, I think one might check
in a test. As you say, intuitively, one is using the same number of bits.
But sometimes math plays funny tricks on you.

  Hans Aberg