# Re: Constant divisions, remainders

## phillips@swanee.ee.uwa.oz.au (Christopher Phillips)Fri, 23 Oct 1992 06:35:07 GMT

From comp.compilers

Related articles
Re: Strength reduction of constant multipliers preston@dawn.cs.rice.edu (1992-10-20)
Re: Constant divisions, remainders Cheryl_Lins@gateway.qm.apple.com (Cheryl Lins) (1992-10-21)
Re: Constant divisions, remainders phillips@swanee.ee.uwa.oz.au (1992-10-23)
Re: Constant divisions, remainders kelsey@flora.ccs.northeastern.edu (1992-10-27)
Re: Constant divisions, remainders torbenm@diku.dk (1992-11-02)
Re: Constant divisions, remainders joe@babel.ho.att.com (1992-11-05)
Re: Constant divisions, remainders henry@zoo.toronto.edu (1992-11-08)
Re: Constant divisions, remainders jones@pyrite.cs.uiowa.edu (1992-11-11)
Re: Constant divisions, remainders nickh@CS.CMU.EDU (1992-11-11)
[4 later articles]
| List of all articles for this month |

 Newsgroups: comp.compilers From: phillips@swanee.ee.uwa.oz.au (Christopher Phillips) Organization: Elec Eng, Univ of Western Australia Date: Fri, 23 Oct 1992 06:35:07 GMT References: 92-10-074 92-10-075 Keywords: arithmetic, optimize

>[Can you turn constant division into simpler operations?]

Some divisions may be performed by a multiplication by a magic number and
a few conditional subtractions.

eg,let M=%10101010 10101011

now, M*3 mod (2^16)=1, hence M*3n mod (2^16)=n.

So, to divide by a number (x) by three, then the following algorithm
may be used.

r:=x*M

if r>2M then ron3=r-2M, remainder=2 else
if r> M then ron3=r- M, remainder=1 else
ron3=r, remainder=0

Similar algorithms may be used for other factors of 2^n+1.
--
Christopher Jam
phillips@swanee.ee.uwa.edu.au
--

Post a followup to this message