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

Thanks to all for your insights. Here is a bit more information that
someone solicited, and which might lead to an optimization which is
obvious to one of you:


*The quotient will almost always be below 2^32, but I prefer not to
make this assumption for this problem.


*The dividend and divisors are both known to be products of primes
between 2 and 67 inclusive, where in some case a prime is represented
more than once. E.g. 2*3*17*17*61 is a legitimate value. The
operands are always unsigned.


*I will be repeatedly dividing by the same divisor. E.g., I start
with a collection of these products and want to determine which, if
any, of these products are divisible by the divisor which is currently
being considered.


-----------------


I tried the 128-bit C incantation which Anton suggested, but got
compiler errors suggesting that I don't have the compiler installed
properly for optimum perfomance. Thanks in advance for any
information as to how to achieve the desired installation status:


[epstein@foo tmp]$ gcc -v
Reading specs from /usr/lib/gcc-lib/i386-redhat-linux/3.2.3/specs
Configured with:
../configure --prefix=/usr --mandir=/usr/share/man --infodir=/usr/share/info
  --enable-shared --enable-threads=posix --disable-checking --with-system-zli
b --enable-__cxa_atexit --host=i386-redhat-linux
Thread model: posix
gcc version 3.2.3 20030502 (Red Hat Linux 3.2.3-49)
[epstein@foo tmp]$ gcc 128bit.c
128bit.c:1: no data type for mode `TI'
[epstein@foo tmp]$ cat 128bit.c
typedef unsigned int uint128_t __attribute__((__mode__(TI)));


main()
{
printf("%d\n",sizeof(uint128_t));
}


I haven't tried any of the other suggestions yet.


Thanks again,


Jonathan
[How about representing the numbers as a bit mask where each bit
represents a prime factor? Allocate a reasonable number of bits for
each factor, e.g., 8 bits for 2, 8 bits for 3, etc. up to a total of,
say 64 or 128 bits, and turn on one bit for each factor, and reserve
one bit at the end of the number for factor overflow if there were
more instances of a factor than would fit in the fields reserved. Now
to test whether A is divisible by B, you need only test if (A&B)==B,
and if that matches and the overflow bit is set in A, you need to go
back and do the division. If you choose your field sizes well, you
should usually be able to get the answer from the AND, which would be
quite fast either on an x86 with MMX or a 64 bit machine. -John]

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