division by 7 without using division operator

Discussion in 'C Programming' started by krypto.wizard@gmail.com, Feb 1, 2007.

  1. Guest

    Last month I appeared for an interview with EA sports and they asked
    me this question.

    How would you divide a number by 7 without using division operator ?

    I did by doing a subtraction and keeping a counter that kept a tab on
    how many times I subtracted.

    Later, the EA sport guy told me that of course there are can be better
    technique by using bit operator.

    Since 7 has a binary representation 111, my guess is that a left shift
    operation of 3 bits should give the answer, but I couldn't get it to
    work.

    Any comments ?
    , Feb 1, 2007
    #1
    1. Advertising

  2. <> wrote in message
    news:...
    > Last month I appeared for an interview with EA sports and they asked
    > me this question.
    >
    > How would you divide a number by 7 without using division operator ?
    >
    > I did by doing a subtraction and keeping a counter that kept a tab on
    > how many times I subtracted.
    >
    > Later, the EA sport guy told me that of course there are can be better
    > technique by using bit operator.


    The most obvious method is to shift, compare, and conditionally subtract and
    mask a 1 into the quotient (very much like the necessary assembly-language
    on a processor without a native division instruction). This is, however,
    very inefficient. This involves some bit operations, but may not be what
    the interviewer was looking for.

    You might make another post and cross-post to sci.math as well. There may
    be some good answers coming from those folks.

    > Since 7 has a binary representation 111, my guess is that a left shift
    > operation of 3 bits should give the answer, but I couldn't get it to
    > work.


    I'm not sure that the direction you're going is anything except a dead end.
    I'm not aware of a general method in the direction you've suggested that
    will work with division. There are some good approximations (for example,
    1/7 = 1/8 + 1/56 which is approximately equal to 1/8 + 1/64), but I'm not
    aware of an exact method in the direction you're suggesting.

    --
    David T. Ashley ()
    http://www.e3ft.com (Consulting Home Page)
    http://www.dtashley.com (Personal Home Page)
    http://gpl.e3ft.com (GPL Publications and Projects)
    David T. Ashley, Feb 1, 2007
    #2
    1. Advertising

  3. wrote:

    > Last month I appeared for an interview with EA sports and they asked
    > me this question.
    >
    > How would you divide a number by 7 without using division operator ?


    Divide by and truncate to integral result?

    or

    See if a number is divisible by 7 with no remainder?
    Christopher Layne, Feb 1, 2007
    #3
  4. CBFalconer Guest

    wrote:
    >
    > Last month I appeared for an interview with EA sports and they
    > asked me this question.
    >
    > How would you divide a number by 7 without using division operator?
    >
    > I did by doing a subtraction and keeping a counter that kept a tab
    > on how many times I subtracted.
    >
    > Later, the EA sport guy told me that of course there are can be
    > better technique by using bit operator.
    >
    > Since 7 has a binary representation 111, my guess is that a left
    > shift operation of 3 bits should give the answer, but I couldn't
    > get it to work.


    If you are multiplying (not dividing) then:
    n = 8 * n - n;
    or
    n = (n << 3) - n; /* The latter only for unsigned n. */

    otherwise he was asking you to build a division routine.

    --
    <http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt>

    "A man who is right every time is not likely to do very much."
    -- Francis Crick, co-discover of DNA
    "There is nothing more amazing than stupidity in action."
    -- Thomas Matthews
    CBFalconer, Feb 1, 2007
    #4
  5. wrote:
    > Last month I appeared for an interview with EA sports and they asked
    > me this question.
    >
    > How would you divide a number by 7 without using division operator ?
    >
    > I did by doing a subtraction and keeping a counter that kept a tab on
    > how many times I subtracted.
    >
    > Later, the EA sport guy told me that of course there are can be better
    > technique by using bit operator.
    >
    > Since 7 has a binary representation 111, my guess is that a left shift
    > operation of 3 bits should give the answer, but I couldn't get it to
    > work.
    >
    > Any comments ?
    >



    (num >> 3) + 1 seems to work?
    Jeffrey Stedfast, Feb 1, 2007
    #5
  6. Ben Pfaff Guest

    writes:

    > How would you divide a number by 7 without using division operator ?


    I'd look up the appropriate section in _Hacker's Delight_, which
    not only gives the details of how to transform division by this
    particular constant into multiplication followed by a correction,
    but also explains how to figure out how to divide by any desired
    constant using the same method. With proofs.

    This same question came up, either here or in comp.programming,
    within the last month or so. Try Google Groups to find the
    earlier discussion.
    --
    "Some people *are* arrogant, and others read the FAQ."
    --Chris Dollin
    Ben Pfaff, Feb 1, 2007
    #6
  7. Guest

    How ? For me it sometimes doesn't work.

    For example 26/7 should give us 3.

    26 is 11010 in binary and a right shift of 3 would give us 3 (binary
    11) and adding 1 changes the result.

    Correct me if I am wrong.

    Thanks

    > (num >> 3) + 1 seems to work?
    , Feb 1, 2007
    #7
  8. wrote:
    > How ? For me it sometimes doesn't work.
    >
    > For example 26/7 should give us 3.
    >
    > 26 is 11010 in binary and a right shift of 3 would give us 3 (binary
    > 11) and adding 1 changes the result.
    >
    > Correct me if I am wrong.
    >
    > Thanks
    >
    >> (num >> 3) + 1 seems to work?

    >
    >


    I was going on the assumption that you knew the value to be a multiple
    of 7 to begin with...

    but as someone else pointed out already, the +1 will not be sufficient
    as the original number grows. I was only looking at "small" multiples of 7.

    7, 14, 21, 28, 35, 42, 49...


    It also wasn't clear to me if he wanted exact results or approximations.
    Being that EA Sports is a 3d gaming house, I kinda figured approximation
    is what they were looking for.

    Jeff
    Jeffrey Stedfast, Feb 1, 2007
    #8
  9. writes:
    > Last month I appeared for an interview with EA sports and they asked
    > me this question.
    >
    > How would you divide a number by 7 without using division operator ?

    [...]

    In a number system with wraparound semantics, such as C's unsigned
    integer types (or signed integer types on most two's complement
    implementations), you can often replace division by a constant with
    multiplication by a constant.

    I don't know the details of figuring out what constant to use, but
    some compilers are smart enough to do this. If you can write a small
    program that divides a number by 7 and examine the generated assembly
    listing, you might see a multiplication instruction rather than a
    division instruction.

    <OT>gcc does this; I haven't studied the assembly listing enough to
    understand what's going on, but you might want to.</OT>

    The fact that compilers can perform this optimization -- and, perhaps
    more important, can decide when it is and isn't necessary -- is a good
    reason *not* to bother doing this yourself. Just divide by 7; that's
    what the "/" operator is for.

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
    We must do something. This is something. Therefore, we must do this.
    Keith Thompson, Feb 1, 2007
    #9
  10. Guest

    On Jan 31, 8:03 pm, wrote:
    > Last month I appeared for an interview with EA sports and they asked
    > me this question.
    >
    > How would you divide a number by 7 without using division operator ?
    >
    > I did by doing a subtraction and keeping a counter that kept a tab on
    > how many times I subtracted.
    >
    > Later, the EA sport guy told me that of course there are can be better
    > technique by using bit operator.
    >
    > Since 7 has a binary representation 111, my guess is that a left shift
    > operation of 3 bits should give the answer, but I couldn't get it to
    > work.
    >
    > Any comments ?


    For integers, here's a good way of doing it with 32 bit x86 assembly:

    ; uint32_t udiv_7 (uint32_t eax)
    cmp eax, 0ccccccd1h
    adc eax, 0ffffffffh
    mov edx, 092492493h
    mul edx
    shr edx, 2
    ; value edx

    The problem is that it requires a widening multiply which the C
    standard does not have, so there is no easy way of translating this to
    C.

    For floating point, obviously you would want to multiply by the
    reciprocal of 7. You might then check nearby floating point numbers
    (some that is apparently possible in C99, or if you can assume
    IEEE-754) to see if they are better approximations by multiplying the
    7 back.

    --
    Paul Hsieh
    http://www.pobox.com/~qed/
    http://bstring.sf.net/
    , Feb 1, 2007
    #10
  11. said:

    > Last month I appeared for an interview with EA sports and they asked
    > me this question.
    >
    > How would you divide a number by 7 without using division operator ?


    Easy: q = exp(log(d) - log(7));

    > I did by doing a subtraction and keeping a counter that kept a tab on
    > how many times I subtracted.
    >
    > Later, the EA sport guy told me that of course there are can be better
    > technique by using bit operator.


    I'd have replied that, unless we have some criteria by which to judge,
    that's not better, merely different.

    --
    Richard Heathfield
    "Usenet is a strange place" - dmr 29/7/1999
    http://www.cpax.org.uk
    email: rjh at the above domain, - www.
    Richard Heathfield, Feb 1, 2007
    #11
  12. pete Guest

    wrote:
    >
    > How ? For me it sometimes doesn't work.
    >
    > For example 26/7 should give us 3.
    >
    > 26 is 11010 in binary and a right shift of 3 would give us 3 (binary
    > 11) and adding 1 changes the result.
    >
    > Correct me if I am wrong.


    > > (num >> 3) + 1 seems to work?


    "right shift of 3" is exactly equal to "division by 8"

    (7 >> 3 == 0)
    (8 >> 3 == 1)
    (15 >> 3 == 1)
    (16 >> 3 == 2)

    --
    pete
    pete, Feb 1, 2007
    #12
  13. pete wrote:
    > wrote:
    >> How ? For me it sometimes doesn't work.
    >>
    >> For example 26/7 should give us 3.
    >>
    >> 26 is 11010 in binary and a right shift of 3 would give us 3 (binary
    >> 11) and adding 1 changes the result.
    >>
    >> Correct me if I am wrong.

    >
    >>> (num >> 3) + 1 seems to work?

    >
    > "right shift of 3" is exactly equal to "division by 8"
    >
    > (7 >> 3 == 0)
    > (8 >> 3 == 1)
    > (15 >> 3 == 1)
    > (16 >> 3 == 2)
    >


    I know - it was a "rough estimation" (and also hence the +1)

    anyways, this is a little better:

    (x >> 2) - (x >> 3) + (x >> 6)

    the first 2 terms are a /8, rounded up.

    (7 >> 2) - (7 >> 3) + (7 >> 6) == 1 - 0 + 0 == 1
    (8 >> 2) - (8 >> 3) + (8 >> 6) == 2 - 1 + 0 == 1
    (15 >> 2) - (15 >> 3) + (15 >> 6) == 3 - 1 + 0 == 2
    (16 >> 2) - (16 >> 3) + (16 >> 6) == 4 - 2 + 0 == 2
    (21 >> 2) - (21 >> 3) + (21 >> 6) == 5 - 2 + 0 == 3
    (28 >> 2) - (28 >> 3) + (28 >> 6) == 7 - 3 + 0 == 4
    (35 >> 2) - (35 >> 3) + (35 >> 6) == 8 - 4 + 0 == 4 :(
    ....
    (100 >> 2) - (100 >> 3) + (100 >> 6) == 25 - 12 + 1 = 14
    Jeffrey Stedfast, Feb 1, 2007
    #13
  14. On Wed, 31 Jan 2007 20:03:38 -0800, krypto.wizard wrote:

    > Last month I appeared for an interview with EA sports and they asked
    > me this question.
    >
    > How would you divide a number by 7 without using division operator ?
    >

    <snip>
    >

    If n >= 0 we can compute q>=0 and 0<=r<8 with n = 8*q + r using
    >> and &. So n = 7*q + q+r hence n/7 = q + (q+r)/7. For n>7

    we have q+r < n, so we can iterate.
    Duncan
    Duncan Muirhead, Feb 1, 2007
    #14
  15. In article <>,
    Richard Heathfield <> wrote:

    >> Last month I appeared for an interview with EA sports and they asked
    >> me this question.
    >>
    >> How would you divide a number by 7 without using division operator ?


    >Easy: q = exp(log(d) - log(7));


    The interviewer might well have replied that the purpose of the
    interview was not merely to determine your logical skills, but your
    ability to solve problems that you would be given in the course of
    your job; and they might not always be expressed precisely, so an
    ability to infer what the questioner really wants would be an
    advantage. An insistence on treating questions literally is not
    always regarded as a virtue outside comp.lang.c.

    -- Richard
    --
    "Consideration shall be given to the need for as many as 32 characters
    in some alphabets" - X3.4, 1963.
    Richard Tobin, Feb 1, 2007
    #15
  16. Ico Guest

    wrote:
    > Last month I appeared for an interview with EA sports and they asked
    > me this question.
    >
    > How would you divide a number by 7 without using division operator ?
    >
    > I did by doing a subtraction and keeping a counter that kept a tab on
    > how many times I subtracted.
    >
    > Later, the EA sport guy told me that of course there are can be better
    > technique by using bit operator.
    >
    > Since 7 has a binary representation 111, my guess is that a left shift
    > operation of 3 bits should give the answer, but I couldn't get it to
    > work.



    Pick your accuracy:

    a: the required multiplication
    b: the resulting factor from the operation

    + (a>>3)
    a=0.142857 b=0.125 error=1.7857%

    + (a>>3) + (a>>6)
    a=0.142857 b=0.140625 error=0.2232%

    + (a>>3) + (a>>6) + (a>>9)
    a=0.142857 b=0.142578 error=0.0279%

    + (a>>3) + (a>>6) + (a>>9) + (a>>12)
    a=0.142857 b=0.142822 error=0.0035%

    + (a>>3) + (a>>6) + (a>>9) + (a>>12) + (a>>15)
    a=0.142857 b=0.142853 error=0.0004%

    + (a>>3) + (a>>6) + (a>>9) + (a>>12) + (a>>15) + (a>>18)
    a=0.142857 b=0.142857 error=0.0001%

    + (a>>3) + (a>>6) + (a>>9) + (a>>12) + (a>>15) + (a>>18) + (a>>21)
    a=0.142857 b=0.142857 error=0.0000%

    --
    :wq
    ^X^Cy^K^X^C^C^C^C
    Ico, Feb 1, 2007
    #16
  17. Ben Pfaff Guest

    Jeffrey Stedfast <> writes:

    > I was going on the assumption that you knew the value to be a multiple
    > of 7 to begin with...


    If x is a unsigned 32-bit integer that is a multiple of 7, then
    you can divide by 7 with simply:
    x *= 0xb6db6db7;
    --
    "I've been on the wagon now for more than a decade. Not a single goto
    in all that time. I just don't need them any more. I don't even use
    break or continue now, except on social occasions of course. And I
    don't get carried away." --Richard Heathfield
    Ben Pfaff, Feb 1, 2007
    #17
  18. Richard Tobin said:

    > In article <>,
    > Richard Heathfield <> wrote:
    >
    >>> Last month I appeared for an interview with EA sports and they asked
    >>> me this question.
    >>>
    >>> How would you divide a number by 7 without using division operator ?

    >
    >>Easy: q = exp(log(d) - log(7));

    >
    > The interviewer might well have replied that the purpose of the
    > interview was not merely to determine your logical skills, but your
    > ability to solve problems that you would be given in the course of
    > your job;


    Yup - and this solution works just fine.

    > and they might not always be expressed precisely, so an
    > ability to infer what the questioner really wants would be an
    > advantage. An insistence on treating questions literally is not
    > always regarded as a virtue outside comp.lang.c.


    I think you're arguing from prejudice - that is, I believe you've made an
    assumption about the interviewer's expectations. That isn't necessarily a
    wise strategy. To give you a different example, if the interviewer asked
    you what was wrong with this program:

    #include <stdio.h>
    #include <stdlib.h>
    #include <strlen.h>
    #include <assert.h>

    main(int c, char **v)
    {
    char *p = malloc(strlen(v[0]));
    char *q, *r;
    assert(p);
    strcpy(p, v[0]);
    q = p;
    r = q + strlen(p) - 1;
    while(q < r)
    {
    char c = *q; *q++ = *r; *r-- = c;
    }
    puts(p);
    }

    how would you reply? What do you think the questioner really wants?

    --
    Richard Heathfield
    "Usenet is a strange place" - dmr 29/7/1999
    http://www.cpax.org.uk
    email: rjh at the above domain, - www.
    Richard Heathfield, Feb 1, 2007
    #18
  19. In article <>,
    Ben Pfaff <> wrote:

    >If x is a unsigned 32-bit integer that is a multiple of 7, then
    >you can divide by 7 with simply:
    > x *= 0xb6db6db7;


    .... because 0xb6db6db7 * 7 is 0x500000001, so 7y * 0xb6db6db7 is
    y * 0x500000001, which is congruent to y mod 2^32.

    Even more off-topic:

    I used a similar trick years ago in Minix, which had no function for
    sleeping less than a second. Internally, it slept in units of 1/60
    second, and carelessly multiplied the argument to sleep() by 60. By
    passing a suitable large number, one could arrange for the overflow to
    produce a desired fraction of a second:

    /* Sleep for t milliseconds (resolution 1/15 second). Assumes 32-bit ints. */

    void msleep(t)
    int t;
    {
    int s, f;

    f = (t * 15 + 500) / 1000;

    s = f / 15; f = f % 15;

    sleep(s + 787410671 * f);

    }

    -- Richard
    --
    "Consideration shall be given to the need for as many as 32 characters
    in some alphabets" - X3.4, 1963.
    Richard Tobin, Feb 1, 2007
    #19
  20. In article <>,
    Richard Heathfield <> wrote:

    >> and they might not always be expressed precisely, so an
    >> ability to infer what the questioner really wants would be an
    >> advantage. An insistence on treating questions literally is not
    >> always regarded as a virtue outside comp.lang.c.


    >I think you're arguing from prejudice - that is, I believe you've made an
    >assumption about the interviewer's expectations. That isn't necessarily a
    >wise strategy.


    Nonetheless, I think my assumption is likely to be right. Obviously
    the best thing to do would be to verify that assumption before
    answering the question. Just giving the answer you suggested does not
    seem like a good strategy.

    >To give you a different example, if the interviewer asked
    >you what was wrong with this program:
    >
    >#include <stdio.h>
    >#include <stdlib.h>
    >#include <strlen.h>
    >#include <assert.h>
    >
    >main(int c, char **v)
    >{
    > char *p = malloc(strlen(v[0]));
    > char *q, *r;
    > assert(p);
    > strcpy(p, v[0]);
    > q = p;
    > r = q + strlen(p) - 1;
    > while(q < r)
    > {
    > char c = *q; *q++ = *r; *r-- = c;
    > }
    > puts(p);
    >}
    >
    >how would you reply?


    "You aren't Richard Heathfield by any chance, are you?"

    >What do you think the questioner really wants?


    I would assume that the interviewer realised that there were several
    errors of varying seriousness, and that he wanted me to list them. Of
    course, I might be wrong, but such is life.

    -- Richard
    --
    "Consideration shall be given to the need for as many as 32 characters
    in some alphabets" - X3.4, 1963.
    Richard Tobin, Feb 1, 2007
    #20
    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. Manish_Ganvir
    Replies:
    13
    Views:
    1,553
    Keith Thompson
    Feb 14, 2005
  2. Sri

    Implementing the division operator

    Sri, May 1, 2006, in forum: C Programming
    Replies:
    13
    Views:
    4,102
  3. Replies:
    1
    Views:
    955
    Alf P. Steinbach
    Jan 19, 2007
  4. spl

    How to replace /(division) operator

    spl, Apr 25, 2008, in forum: C Programming
    Replies:
    14
    Views:
    1,567
    Tomás Ó hÉilidhe
    May 3, 2008
  5. Michael Neumann
    Replies:
    29
    Views:
    338
    Michael Neumann
    Jun 11, 2004
Loading...

Share This Page