two possible coding porjects

[Kevin Ryde]

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.