Re: Constant divisions, remainders

rutt@paradise.mti.sgi.com writes:
>I was curious as to whether you have any ideas about divisons and remainders
>by constants. Of course the powers of 2 are easy, but what about the more
>interesting cases.


The idea for non 2^i cases is to use a reciprocal. Here are some references
that discuss this idea.


@inproceedings{alverson:91,
author = "Robert Alverson",
title = "Integer division using reciprocals",
booktitle = "Proceedings 10th IEEE Symposium on
Computer Arithmetic",
pages = "186--190",
address = "Grenoble, France",
month = jun,
year = 1991}


@inproceedings{srinivasan:90,
author = "P. Srinivasan and T.R.N. Rao and F.E. Petry",
title = "An integer division method using characteristics
of integer reciprocals",
booktitle = "Proceedings 1990 Southeastcon",
pages = "462--466",
month = apr,
year = 1990}


@inproceedings{fowler:89,
author = "D.L. Fowler and J.E. Smith",
title = "An accurate, high speed implementation of division
by reciprocal approximation",
booktitle = "Proceedings 9th IEEE Symposium on Computer
Arithmetic",
pages = "60--67",
month = sep,
year = 1989}


@inproceedings{magenheimer:87,
author = "D.J. Magenheimer and L. Peters and K. Pettis and
D. Zuras",
title = "Integer multiplication and division on the HP
precision architecture",
booktitle = asplos2,
pages = "90--99",
address = "Palo Alto, CA",
month = oct,
year = 1987}


@article{li:85,
author = "S.-Y. R. Li",
title = "Fast constant division routines",
journal = "IEEE Transactions on Computers",
volume = 34,
number = 9,
pages = "866--869",
month = sep,
year = 1985}


@article{artzy:76,
author = "E. Artzy and J.A. Hinds and H.J. Saal",
title = "A fast division technique for constant divisors",
journal = CACM,
volume = 19,
number = 2,
pages = "98--101",
month = feb,
year = 1976}


Cheryl Lins, Oberon-2 Paladin. lins@apple.com
--

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