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)
Constant divisions, remainders rutt@paradise.mti.sgi.com (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

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