20 May 2005 16:08:18 -0400

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

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 |

Posted-Date: | 20 May 2005 16:08:18 EDT |

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.