«

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 ?

<> wrote in message
news: oups.com...
> 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)

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?

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

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?

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

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?

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

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) kst- <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.

On Jan 31, 8:03 pm, krypto.wiz...@gmail.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.
>
> 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/