Re: division by 7efficiently

Jón Fairbairn <jon.fairbairn@xxxxxxxxxxxx> writes:

"eKo1" <berndlosert@xxxxxxxxxxxx> writes:

On Feb 1, 2:28 pm, "Krypto" <krypto.wiz...@xxxxxxxxx> wrote:
The correct answer as told to me by a person is

(N>>3) + ((N-7*(N>>3))>>3)

The above term always gives division by 7

N >> 3 is the same as dividing the number by eight so you have that
(N>>3) + ((N-7*(N>>3))>>3) = N/8 + (N - 7(N/8))/8 = N/8 + N/8 - 7N/64
= 2N/8 - 7N/64 = (16N - 7N) / 64 = 9/64 N.

9/64 = 0.140625
1/7 = 0.14285714285714285...

Close, but no cigar.

I suspect that what the interviewer was looking for was
something like:

division by 7 is the same as multiplication by 1/7. 1/7 in
binary is 0.001001001... (1/8 + 1/64 + 1/512 + ...)

So if you repeat "add N>>3 and shift the result 3 places
right" until it stops changing, you've got N/7 -- except
that if you do this in integer arithmetic it treats
0.111... as 0 when it really means 1. Correcting for that is
left as an exercise for the reader ;-)

You can do even better than this, by exploiting the periodicity of 1/7
to double the number of correct bits per step (instead of just adding
three correct bits per step):

x = N>>3; /* N * 0.001 */
x += x>>3; /* N * 0.001001 */
x += x>>6; /* N * 0.001001001001 */
x += x>>12; /* N * 0.001001001001001001001001 */
x += x>>24; /* N * 0.001001001001001001001001001001001001001001001001 */

There is still the problem of rounding, though. You can do this by
multiplying by 8/7 and then use the last bits to determine rounding
when doing a final shift:

x = N + (N>>3); /* N * 1.001 */
x += x>>6; /* N * 1.001001001 */
x += x>>12; /* N * 1.001001001001001001001 */
x += x>>24; /* N * 1.001001001001001001001001001001001001001001001 */
x = (x>>3) + (x&4 ? 1 : 0);
/* Divide by 8 and round up if last bits are >=4 */

Note that this assumes N>=0 and that N*8/7 fits within integers.
Note, also, that the above rounds the result, so it is not the same as
integer division. You can get closer to integer division if you only
round up if the last three bits before the last shift are all 1, i.e.,
by replacing the last line by:

x = (x>>3) + ((x&7)==7 ? 1 : 0);
/* Divide by 8 and round up if last bits are =7 */

It is not exactly the same as integer division, though. A test
program reveals that for 12 values of N under 1000 the above gives a
result that is one less than N/7. You can get more exact division at
the cost of reducing the highest allowable value of N by changing the
above to:

x = N + (N<<3); /* N * 1001 */
x += x>>6; /* N * 1001.001001 */
x += x>>12; /* N * 1001.001001001001001001 */
x += x>>24; /* N * 1001.001001001001001001001001001001001001001001 */
x = (x>>6) + ((x&63)==63 ? 1 : 0);
/* Divide by 64 and round up if last bits are = 63 */

Now, the smallest N that goes wrong is 28679 and there are "only" 288
Ns below 100000 that go wrong. You can trade range of N and exactness
of division even more, e.g., by:

x = N + (N<<3); /* N * 1001 */
x += x<<6; /* N * 1001001001. */
x += x>>12; /* N * 1001001001.001001001001 */
x += x>>24; /* N * 1001001001.001001001001001001001001001001001001 */
x = (x>>12) + ((x&4095)==4095 ? 1 : 0);
/* Divide by 2^12 and round up if last bits are = 2^12-1 */

Now it is exact up to N = 7*2^20 = 7340032, but it runs into overflow
problems when N is greater.

So, if you want fast integer division by 7 and you know N <= 7*2^20
(and you use 32-bit unsigned integers), you can use the above.

The method used above is fairly general: calculate exactly until the
period starts repeating, then use shifting to double the number of
periods at each step. It gets a bit more complicated if there are
bits before the period starts, but you can add these in later.

Torben
.

Relevant Pages

  • Re: Fractional Remainder
    ... To quote Rick Rothstein from the "Decimal Display" ... The VB Mod function only works with integral values, and it Rounds (using ... Banker's Rounding) and number containing fractions BEFORE it performs the ... I don't remember if you can get away with integer division in the first line ...
    (microsoft.public.vb.general.discussion)
  • Re: C++ more efficient than C?
    ... The shift operations in C are defined for < sizeofwhile ... Seed7 and was under the impression that C++ decided to ... compiler. ... This situation can be compared to the integer division. ...
    (comp.programming)
  • Re: left shifts (rationale question)
    ... A right shift of k bits can be interpreted as integer division by 2^k; ... "Consideration shall be given to the need for as many as 32 characters ... in some alphabets" - X3.4, ...
    (comp.lang.c)
  • Re: Pixel Mania
    ... truncated number that VB rounds to 15 displayed digits is an integer ... power of two (I think it is only considered as a decimal if the power of ... Questions about why an expected integer division answer wasn't occurring ... integer operands in integer division; but, hey, I have seen questions here ...
    (microsoft.public.vb.general.discussion)
  • Re: real basic..
    ... "by convention, integer division always rounds down, even in cases like ... Sta parlando della stessa cosa, ma prima diceva "rounds down", ora ... esorta a ricordare che "truncates". ...
    (it.comp.macintosh)