Re: 96-bit integer modulo, Athlon64 gcc 64-bit integers, libc codefor 64-bit division, etc.

  "Jonathan Epstein" <Jonathan_Epstein@nih.gov> wrote:


> To effectively solve a research problem, I need a very fast
> (sub-microsecond, if possible) method to determine whether one 96-bit
> integer is an exact multiple of another 96-bit integer.
>
> The high-level application is mostly written in Perl and is intended
> to be portable, but right now I am concentrating on the hardware that
> I have in-hand, which include 2.4 GHz Xeons, a 1.8 GHz Athlon64
> ("3000+), a 1.8GHz Pentium M, and a Mac with a G5 CPU (sorry, I don't
> know the CPU speed). The x86s (except for the Pentium M) are running
> Linux, the Pentium M is running Windows XP and the Mac is running OS
> X.


You could take the G5 with gcc C compiler (part of XCode), turn
compiler options on to make long double = 128 bit floating-point with
about 103 bits of precision.


If you had IEEE 754 floating-point arithmetic, you could just
calculate t = x/y and check whether t == floor (t). But 128 long
double doesn't use IEEE 754, so you have to be a bit more careful.


Calculate t = floorl (x/y + 0.5) and check whether t*y == x. t will be
an integer. If x is _not_ a multiple of y, then t*y != x, no matter
what the value of t is, and long double gives you enough precision so
that rounding errors won't change this. If x _is_ a multiple of y,
then t will be exactly equal to x/y, since the rounding errors are too
small to change this, and x*t will be equal to y.


If you use 128 bit long double with values that are actually integers
with less than 100 bits, then add, subtract and multiply will give you
the correct results, and the implementation is quite fast. I would
think this will be below 0.2 microseconds per test.

Return to the comp.compilers page.
Search the comp.compilers archives again.