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

"Jonathan Epstein" <Jonathan_Epstein@nih.gov>
20 May 2005 16:08:18 -0400

          From comp.compilers

Related articles
[5 earlier articles]
Re: 96-bit integer modulo, Athlon64 gcc 64-bit integers, libc codefor gah@ugcs.caltech.edu (glen herrmannsfeldt) (2005-05-15)
Re: 96-bit integer modulo, Athlon64 gcc 64-bit integers, libc codefor anton@mips.complang.tuwien.ac.at (2005-05-15)
Re: 96-bit integer modulo, Athlon64 gcc 64-bit integers, libc codefor christian.bau@cbau.freeserve.co.uk (Christian Bau) (2005-05-15)
Re: 96-bit integer modulo, Athlon64 gcc 64-bit integers, libc codefor gah@ugcs.caltech.edu (glen herrmannsfeldt) (2005-05-15)
Re: 96-bit integer modulo, Athlon64 gcc 64-bit integers, libc codefor anton@mips.complang.tuwien.ac.at (2005-05-16)
Re: 96-bit integer modulo, Athlon64 gcc 64-bit integers, libc codefor Jonathan_Epstein@nih.gov (Jonathan Epstein) (2005-05-16)
Re: 96-bit integer modulo, Athlon64 gcc 64-bit integers, libc codefor Jonathan_Epstein@nih.gov (Jonathan Epstein) (2005-05-20)
| List of all articles for this month |

From: "Jonathan Epstein" <Jonathan_Epstein@nih.gov>
Newsgroups: comp.compilers
Date: 20 May 2005 16:08:18 -0400
Organization: Compilers Central
References: 05-05-063 05-05-150
Keywords: arithmetic, performance

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]
>



Post a followup to this message

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