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

Thanks, John, this is a good idea.


Since the maximum number of occurences of each prime is known in
advance, for now I'm just encoding one bit for each prime factor,
which in practice works out to about 400 bits, and runs at about the
same speed as my native 64-bit modulo operations. This is a bit
wasteful, but nice & simple. I may adopt either your suggested
refinement or some related refinements at some point, but for now I'm
free from integer multiplication/division and word size limits.


Thanks again to all who responded.


Jonathan


"Jonathan Epstein" <Jonathan_Epstein@nih.gov> wrote in message
> [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.