16 May 2005 23:02:38 -0400

From: | "Jonathan Epstein" <Jonathan_Epstein@nih.gov> |

Newsgroups: | comp.compilers |

Date: | 16 May 2005 23:02:38 -0400 |

Organization: | Compilers Central |

References: | 05-05-063 |

Keywords: | arithmetic, performance |

Posted-Date: | 16 May 2005 23:02:38 EDT |

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]

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.