# two possible coding porjects

**Kevin Ryde
**
user42@zip.com.au

*Fri, 01 Aug 2003 08:06:56 +1000*

stephen-nuchia@utulsa.edu writes:
>*
*>* 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
normal use.
>* 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.