division by 7 without using division operator

K

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 ?
 
D

David T. Ashley

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.
 
C

Christopher Layne

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?
 
C

CBFalconer

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
 
J

Jeffrey Stedfast

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?
 
B

Ben Pfaff

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.
 
K

krypto.wizard

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
 
J

Jeffrey Stedfast

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

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
 
K

Keith Thompson

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.
 
W

websnarf

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.
 
R

Richard Heathfield

(e-mail address removed) 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.
 
P

pete

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.

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

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

Jeffrey Stedfast

pete said:
"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
 
D

Duncan Muirhead

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 ?
If n >= 0 we can compute q>=0 and 0<=r<8 with n = 8*q + r usingwe have q+r < n, so we can iterate.
Duncan
 
R

Richard Tobin

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 ?
[/QUOTE]
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
 
I

Ico

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%
 
B

Ben Pfaff

Jeffrey Stedfast said:
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;
 
R

Richard Heathfield

Richard Tobin said:
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;[/QUOTE]

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?
 
R

Richard Tobin

Ben Pfaff said:
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
 
R

Richard Tobin

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.
[/QUOTE]
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
 

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,734
Messages
2,569,441
Members
44,832
Latest member
GlennSmall

Latest Threads

Top