Re: integer divide by 7 trick?

Discussion in 'C++' started by MG, Jul 20, 2003.

  1. MG

    MG Guest

    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:...
    > 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 = 7<<i;
    > if(seventimes2pow > val)
    > break;
    > }
    >
    > i--;
    > while(i>=0) {
    > if(seventimes2pow <= val) {
    > val -= seventimes2pow;
    > result += 1<<i;
    > }
    > i--;
    > }
    >
    > return result;
    > }
     
    MG, Jul 20, 2003
    #1
    1. Advertising

  2. MG

    Roy Smith Guest

    Just out of curiosity, what's wrong with "i / 7"?
     
    Roy Smith, Jul 21, 2003
    #2
    1. Advertising

  3. 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.
     
    Stewart Gordon, Jul 21, 2003
    #3
  4. 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 =---
     
    Mark McIntyre, Jul 22, 2003
    #4
  5. MG

    MG Guest

    "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..
     
    MG, Jul 22, 2003
    #5
  6. 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.
     
    Christian Bau, Jul 22, 2003
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Robert W Hand

    Re: integer divide by 7 trick?

    Robert W Hand, Jul 20, 2003, in forum: C++
    Replies:
    12
    Views:
    712
    Paul Hsieh
    Jul 25, 2003
  2. JS
    Replies:
    1
    Views:
    336
    Peter van Merkerk
    Jul 22, 2003
  3. yvan joffre

    Re: integer divide by 7 trick?

    yvan joffre, Jul 25, 2003, in forum: C++
    Replies:
    3
    Views:
    301
    Stewart Gordon
    Jul 25, 2003
  4. MG

    Re: integer divide by 7 trick?

    MG, Jul 20, 2003, in forum: C Programming
    Replies:
    5
    Views:
    3,971
    Christian Bau
    Jul 22, 2003
  5. Robert W Hand

    Re: integer divide by 7 trick?

    Robert W Hand, Jul 20, 2003, in forum: C Programming
    Replies:
    12
    Views:
    622
    Paul Hsieh
    Jul 25, 2003
Loading...

Share This Page