division by 7 without using division operator

[krypto.wizard]

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 ?

[Richard Heathfield]

kr***********@g mail.com 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.

[pete]

kr***********@g mail.com 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

[Jeffrey Stedfast]

pete wrote:

kr***********@g mail.com 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

[Richard Tobin]

In article <yp************ *********@bt.co m>,
Richard Heathfield <rj*@see.sig.in validwrote:

>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
--
"Considerat ion shall be given to the need for as many as 32 characters
in some alphabets" - X3.4, 1963.

[Ico]

kr***********@g mail.com 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

[Duncan Muirhead]

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

[Ben Pfaff]

Jeffrey Stedfast <st******@comca st.netwrites:

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

[Richard Heathfield]

Richard Tobin said:

In article <yp************ *********@bt.co m>,
Richard Heathfield <rj*@see.sig.in validwrote:

>>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 Tobin]

In article <87************ @blp.benpfaff.o rg>,
Ben Pfaff <bl*@cs.stanfor d.eduwrote:

>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
--
"Considerat ion shall be given to the need for as many as 32 characters
in some alphabets" - X3.4, 1963.

[Richard Tobin]

In article <m-*************** *************** @bt.com>,
Richard Heathfield <rj*@see.sig.in validwrote:

>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
--
"Considerat ion shall be given to the need for as many as 32 characters
in some alphabets" - X3.4, 1963.