[LiDIA] want fast bit set/extract

[LiDIA Administrator]

Hi,

On Sat, Apr 17, 2004 at 02:45:45AM -0000, D. J. Bernstein wrote:
> I often want to compute floor(n/2^s) mod 2^b, given n,b,s. This should
> be extremely fast when b is small (particularly when s is a multiple of
> 32), even if s is somewhere in the middle of the bits of n.
> 
> Similarly, I often want to replace n with n + 2^s m. This should be
> extremely fast (assuming few carries) when m is small and n already has
> enough space allocated.
> 
> Please support these two operations! These are _much_ more useful than
> isolated right-shift/left-shift operations.

For the most part, LiDIA does not perform the multi precision
computations itself but delegates them to third party libraries - by
default to GMP, but LiDIA can be configured to interface to other
libraries as well. Thus, LiDIA can only offer an *efficient*
implementation of the functions you request if the underlying MP
library allows it to do so.

Right now I am not sure whether you ask the GMP developers to add
new functions (that should eventually be made accessible through
LiDIA) or whether you want me to implement such functions using the
existing GMP interface.
If you have an implementation of the functions mentioned above that
uses GMP only and is as efficient as you want it to be then we can
discuss how to extend LiDIA's bigint interface in order to facilitate
a comparable performance gain when using LiDIA on top of GMP. (It
might be necessary to provide naive fallbacks if LiDIA is built above
another MP library but I don't expect this to be a problem.)

Regards

Christoph Ludwig
-- 
http://www.informatik.tu-darmstadt.de/TI/Mitarbeiter/cludwig.html
LiDIA: http://www.informatik.tu-darmstadt.de/TI/LiDIA/Welcome.html