division by 7 efficiently ???

[John Machin]

On Feb 2, 11:03 pm, "Bart Ogryczak" <B.Ogryc... at gmail.com> wrote:
> On Feb 1, 3:42 am, krypto.wiz... at gmail.com wrote:
>
> > How to divide a number by 7 efficiently without using - or / operator.
> > We can use the bit operators. I was thinking about bit shift operator
> > but I don't know the correct answer.
>
> It´s quiet simple. x ==  8*(x/8) + x%8, so x == 7*(x/8) + (x/8 + x%8)
> x/8 == x>>3, x%8 == x&7
> And there you have it, function rounds upwards for numbers not
> divisible by 7. Gotta change int(x>0) to int(x>3) to round normally,
> or int(x>6) to round downwards.
>
> def d7(x):
>         if(x>>3 == 0): return int(x>0)
>         return (x>>3)+d7((x>>3)+(x&7))

I doubt that a recursive function call (even a tail-recursive one)
comes near what the OP and his interrogators mean by "efficiently".

Nicko has already given the answer for the case where a 31-bit non-
negative dividend is required. Here are some examples of the technique
for cases where smaller numbers are found e.g. in date arithmetic.

def div7a(N):
    assert 0 <= N <= 684
    r = (N << 3) + N
    r = (r << 3) + N
    r = (r << 2) + N
    r >>= 11
    return r

def div7b(N):
    assert 0 <= N <= 13109
    r = (N << 3) + N
    r = (r << 3) + N
    r = (r << 3) + N
    r = (r << 3) + N
    r = (r << 1) + N
    r >>= 16
    return r

What's going on there? Well, using the first example, (2 ** 11) // 7
and rounded to the higher integer is 293.  So 293 / 2048 is an
approximation to 1 / 7. Dividing by 2048 is a doddle. The shift-left-
add stuff is doing the multiplication by 293, unrolled loop, one cycle
per line when implemented as a SHLnADD instruction from the HP PA-RISC
architecture.  Unsigned division otherwise would take 32 DS (divide
step) instructions.

FWIW, gcc emits code for the Intel IA32 architecture that gloriously
"misuses" the LEAL instruction to get the same reg1 = (reg2 << n) +
reg3 effect.

Any relevance to this newsgroup? Yes, there's a lot of pre-computation
involved there. Python is an excellent language for debugging such
stuff and generating include files for a production code.

Cheers,
John