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