Re: division by 7 efficiently
- From: "Arthur J. O'Dwyer" <ajonospam@xxxxxxxxxxxxxx>
- Date: Thu, 1 Feb 2007 01:47:02 -0500 (EST)
On Thu, 31 Jan 2007 krypto.wizard@xxxxxxxxx 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.
Wrong. Well, technically you /could/ do division that way --- you
could call it the "caveman" method, since maybe a particularly dumb
caveman might do that with pebbles --- but it would be hopelessly
slow. Namely, it's O(2**n) for an n-digit number.
Later, the EA sport guy told me that of course there are can be better
technique by using bit operator.
Yes. If you had a compiler handy, and wanted to impress the interviewer
with your knowledge of other people's knowledge of mathematics, you
could also do it this way:
int bar(int x)
{
int y = ((long long)x * -1840700269) >> 32;
return ((x + y) >> 2) + (x < 0);
}
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.
Left-shifting a value by 3 multiplies it by 2**3 = 8. That's not the
right constant, or the right operation.
Any comments ?
Yes; you're not ready to program games for a living yet.
-Arthur
.
- Follow-Ups:
- Re: division by 7 efficiently
- From: Rob Thorpe
- Re: division by 7 efficiently
- From: krypto . wizard
- Re: division by 7 efficiently
- References:
- division by 7 efficiently
- From: krypto . wizard
- division by 7 efficiently
- Prev by Date: division by 7 efficiently
- Next by Date: Re: division by 7 efficiently
- Previous by thread: division by 7 efficiently
- Next by thread: Re: division by 7 efficiently
- Index(es):
Relevant Pages
|
