«

how about trying this in the first approach:

(val<<5 - val)>>6

this shd give a better apprimate than first right shift and subtracting....

"krazyman" <> wrote in message
news: om...
> Does anyone know a good trick to perform an integer divide by 7
> (the equivalent of x/7 in C) without using a divide? I'm familiar
> with the multiply by 7 trick (x<<3-x), and I was asked this question
> with the implication that something similar exists for divide-by-7. I
> came up with these 2 ways below, but the fast one is inaccurate and
> the correct one probably takes too many cpu cycles to be an
> optimization over the straight integer divide instruction.
>
> ------------------------------------
> #include <stdio.h>
>
> unsigned int ApproximateDiv7(unsigned int val) {
> // 1/7 = 1/8 + 1/56 =~ 1/8 + 1/64,
> // and 1/64 is much easier to compute than 1/56.
> // still, the returned value will be off by as
> // much as 1/56-1/64 =~ .2%, or more for small values
> // due to truncation
>
> return (val >> 3) + (val >> 5);
> }
>
> // do integer divide by 7 without using division
> unsigned int Div7(unsigned int val) {
> // this works in O(log2(val)) time
>
> unsigned int seventimes2pow[32];
> unsigned int result=0;
> int i;
>
> for(i=0;i<32;i++) {
> seventimes2pow[i] = 7<<i;
> if(seventimes2pow[i] > val)
> break;
> }
>
> i--;
> while(i>=0) {
> if(seventimes2pow[i] <= val) {
> val -= seventimes2pow[i];
> result += 1<<i;
> }
> i--;
> }
>
> return result;
> }

Just out of curiosity, what's wrong with "i / 7"?

On 21/7/03 4:35 pm (UK time), Roy Smith let loose these words:

> Just out of curiosity, what's wrong with "i / 7"?

In case you hadn't noticed, the OP is looking for a method that is
faster than the hardware divide function or whatever the compiler
generates for that code.

Stewart.

--
My e-mail is valid but not my primary mailbox. Please keep replies on
on the 'group where everyone may benefit.

On Mon, 21 Jul 2003 18:49:19 +0100, in comp.lang.c , Stewart Gordon
<> wrote:

>On 21/7/03 4:35 pm (UK time), Roy Smith let loose these words:
>
>> Just out of curiosity, what's wrong with "i / 7"?
>
>In case you hadn't noticed, the OP is looking for a method that is
>faster than the hardware divide function or whatever the compiler
>generates for that code.

He's very unlikely to find one, any well written compiler ought to be
aware of any integer divide tricks.

IMHO its more likely a homework question. I have to say, submitting
such to CLC is likely to get one an F--, because there's almost no
chance of understanding the responses, and parroting them back at your
teacher will make it VERY obvious how you found the "answer"....



--
Mark McIntyre
CLC FAQ <http://www.eskimo.com/~scs/C-faq/top.html>
CLC readme: <http://www.angelfire.com/ms3/bchambless0/welcome_to_clc.html>


----== Posted via Newsfeed.Com - Unlimited-Uncensored-Secure Usenet News==----
http://www.newsfeed.com The #1 Newsgroup Service in the World! >100,000 Newsgroups
---= 19 East/West-Coast Specialized Servers - Total Privacy via Encryption =---

"Stewart Gordon" <> wrote in message
news:bfh0t5$1k1$...
> MG wrote:
>
> > how about trying this in the first approach:
> >
> > (val<<5 - val)>>6
> >
> > this shd give a better apprimate than first right shift and
subtracting....
> <snip>
>
> I presume you've tried that formula for something other than the case
val=0?
>
Frankly speaking...i havent tried it..but it shd work better than the
original alogorithm declared by Krazyman..

In article <pv5Ta.56$>,
"MG" <> wrote:

> "Stewart Gordon" <> wrote in message
> news:bfh0t5$1k1$...
> > MG wrote:
> >
> > > how about trying this in the first approach:
> > >
> > > (val<<5 - val)>>6
> > >
> > > this shd give a better apprimate than first right shift and
> subtracting....
> > <snip>
> >
> > I presume you've tried that formula for something other than the case
> val=0?
> >
> Frankly speaking...i havent tried it..but it shd work better than the
> original alogorithm declared by Krazyman..

I would first change it to

((val << 5) - val) >> 6

because I don't want to look up priorities of << and -, and (val << (5 -
val)) >> 6 would be nonsense.

And this expression calculates val * 31 / 64 which doesn't look like it
is anywhere near val / 7.