div2 and nails

Niels Möller nisse at lysator.liu.se
Thu Dec 11 17:04:27 CET 2003


What's the proper definition of div2 with nails? In particular, how
should the bits be laid out in the input to div2? Each input number is
two words. For clarity, I'll assume that we have 32-bit words and 2bit
nails, generalizations should be easy. Then bits could be distributed
in at least these three ways:

    high word                        low word
A. |xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx|xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx|

   64 significant bits, i.e. all bits in the input are used, just like
   in the non-nail case.

B. |00xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx|00xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx|
   
   60 significant bits, each input word contains 30 bits, and 2 nail
   bits which must be zero.

C. |0000xxxxxxxxxxxxxxxxxxxxxxxxxxxx|xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx|
   
   60 significant bits. The least significant word gets 32 bits, and
   the most significant word gets 28 bits, and 4 nail bits which are
   zero.

Alternatively, the "must be zero" part could be replaced with "the
nail bits are ignored".

A and C have the drawback that one may need bits from more than two
limbs to assemble one div2 input word. B has the drawback that the
layout is incompatible with that used by sub_ddmmss, which is
blissfully ignorant of any nail usage.

So what's the Right Thing to do?

/Niels


More information about the gmp-devel mailing list