Table of Contents
This chapter comments the main design decisions concerning the MPFQ library. Reading this chapter is not an absolute necessity, but helps understanding the logic behind MPFQ
The most important decision concerning MPFQ is the use of automatically generated code for a wide variety of uses. This is a necessity called for by the efficiency requirements. Obviously it comes with pros and cons, some of which will be explained right below
Generating code automatically enables some benefits which are hardly accessible with static code. The first thing to note is that obviously, special-purpose code, fitted for finite fields satisfying some specified characteristics, may only be issued when these characteristics are known, in compile time.
The data type for finite fields elements is not fixed. It can be trimmed down to only the necessary information. This has the consequence that at least in the cases of
and
(respectively, for known word size of 
,
and for known value of 
), the storage
size of finite field elements is constant, and
hides no indirection. No reallocation is required. Objects
can be dealt with at any arbitrary place in memory, every
sequence of bytes in memory may be interpreted as a finite
field element.
It is possible to handle small fields at best speed; if only one assembly instruction is needed, then generated code will (or at least, should) be an inline function equivalent to exactly that instruction.
Extending this principle, if assembly instructions very well adapted to the finite field in consideration are available on some given platform, then generated code ought to use these instuctions. Examples of such cases are MMX and SSE2 instructions, useful for multiplications in
.
Using generated code so widely is special to MPFQ and gives an incentive for better dissemination. Having the ability to provide the best possible speed for finite fields known in advance makes MPFQ a goood choice for every situtation where the finite field in which calculations are to be done is known: there is no need to reinvent the wheel. The authors of MPFQ recall having in several occasions re-implemented some dirty interface to finite field operations, only to gain the « expected » improvement from special-purpose code. The very purpose of MPFQ is to address this situation, which existing software libraries do not do.
As can be expected, the road of automatically generated code incurs some difficulties. We felt however that none of these difficulties should bar the efficiency goal set forth for MPFQ. We list here the difficulties that we have considered.
Special-purpose code is, well, special-purpose. This clearly forbids generic compiled code that will « just work » on any finite field. This being said, coherence in typing and function naming, through the MPFQ API makes it possible to re-use source code (much in the way C++ templates work — however MPFQ is entirely in C).