two possible coding porjects
Fri, 01 Aug 2003 08:06:56 +1000
> When an algorithm expects to compute many modular powers
> with the same modulus it seems to me to be worthwhile to
> precompute the tableau.
Sorry, I don't understand, you'll have to show what you mean.
> Furthermore, when your limb quotient
> is found you still have to do a multiplication and a subtraction
> to get the remainder (if it's needed), right? Again not worth
> the candle in ad-hoc computations but if the application commits
> to using one particular divisor for a while it might pay off.
For a fixed divisor the idea is to pre-compute an inverse (either an
approximation to 1/d, or a mod 2^n for REDC). That turns a division
or mod into basically a high-half and a low-half multiply.
> The mpz_array_init trick of lying about the allocation
> size bothers me a great deal.
mpz_array_init is a highly specialized function, not recommended for
> I also chafe at the waste
> of space involved in using a pointer to a malloc block
> to store a single-limb number.
Unfortunately overheads on small values are more or less inevitable in
a general purpose variable precision library.
> If nothing else it
> contributes to fragmentation of the heap and degrades
> locality of reference.
Allocation strategy can at least be controlled by the application
through setting different memory functions.
> On the Alphas I'm using it might always be faster
> to do the shifts from a copy in L1 cache.
Generally shifts are off the dependent chain and hence have a good
chance of being free on a decent superscalar processor.