two possible coding porjects

[Kevin Ryde]

stephen-nuchia@utulsa.edu writes:
>
> I could always work in a convenient power of two.

(REDC uses that for its inverse, but allows any odd modulus.)

> What happens
> when you compute a/b mod n and (a,n)!=1?]

It's (b,n) which is of concern.  A common factor between the modulus
and divisor will mean either the quotient doesn't exist or is not
unique, depending on the dividend.

> True.  Doesn't mean you have to squander resources.  Of course,
> single-limb quantities don't arise often as results of arbitrary
> integer computations

Any program doing lots of work on 1 or 2 limb values doesn't want to
be making library calls for all operations anyway.  So the aim in gmp
is to get such things through with a minimum of fuss, but no more than
that.

> numerator and/or denominator
> of many rational numbers.  (actually, one and zero come up
> fairly often.

These might be good special cases, we've got a tasks list entry to
consider such things.

> Again something that could use better documentation,

The memory sections of the manual cover it.

> For hard-realtime apps I usually
> pick a few block sizes and maintain freelists by block size,
> then keep a best-fit pool for big oddballs.

Actual allocation strategies are outside our scope.

> I'd just as soon not have to think about memory allocation
> when writing number theory code.

You don't, the policy of not shrinking generally means there's only
ever a few reallocs.

> I know you know all this, but I get the feeling you guys focus more
> on the processor pipelines than on the memory hierarchy.

See cache handling under algorithms in the manual.

We've not had much joy introducing prefetching into low level
routines.  It's a bit tricky to do without compromising the
performance from L1 or making loop control difficult (if the chip
doesn't have actual prefetch instructions).