Re: division by 7 efficiently
- From: Logan Shaw <lshaw-usenet@xxxxxxxxxxxxx>
- Date: Thu, 01 Feb 2007 02:07:48 -0600
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.
Later, the EA sport guy told me that of course there are can be better
technique by using bit operator.
How accurate does it need to be? Will 3 or 4 significant figures be
enough? If so, pick a fraction close to 1/7 whose denominator is a
power of 2.
For example, let's pick 2^16 as the denominator. 2^16 / 7 is 9362.28,
so let's pick 9362 as the numerator. Therefore, our fraction is
9362 / 2^16, and our algorithm is:
int divide_by_7 (int n)
{
return (n * 9362) >> 16;
}
A little testing (by comparing that with actual division) shows that
you get better results (for small numbers) if you round up to 9363
instead, so:
int divide_by_7 (int x)
{
return (n * 9363) >> 16;
}
A quick program I wrote shows that for integer division, this gets
the correct answer for all numbers in the range [0 .. 13109].
Maybe that is good enough.
But here's something even more interesting. If I convert 9362 to
binary, I see a sort of a pattern:
10010010010010
In fact, look at the pattern behind 2^64 / 7:
10010010010010010010010010010010010010010010010010010010010010
To me, that seems a *little* too regular to be a coincidence.
In fact, this makes a lot of sense. 1/7 is a repeating fraction in
binary. It's 0.001001001001... . And if you multiply that fraction
by 7 (which is 0b111), you get 0.111111111111..., which equals 1.0.
- Logan
.
- References:
- division by 7 efficiently
- From: krypto . wizard
- division by 7 efficiently
- Prev by Date: Re: division by 7 efficiently
- Next by Date: Re: division by 7 efficiently
- Previous by thread: Re: division by 7 efficiently
- Next by thread: Re: division by 7 efficiently
- Index(es):
Relevant Pages
|
