division by 7 efficiently ???

[krypto.wizard]

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.

 

[Paul Rubin]

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.

Erm, sounds like a homework problem... suggestion: think of how many
input bits you have, then check the accuracy of the obvious
approximations until you reach one that's precise enough.

 

[Ben Finney]

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.

I think you are asking for help on a homework assignment in violation
of collusion and plagiarism rules of your educational institution, and
I claim my ten zorkmids.

Please use the resources made available to you in your course of
study; this almost certainly does not include having people on
discussion forums answer the homework for you.

 

[Steven D'Aprano]

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.

I'd be surprised if there was a trick for dividing by seven efficiently...
it is one of the "difficult" cases. See:

http://www.bitwisemag.com/copy/wilf/wilf5.html

for a discussion.

But even if there is some nifty algorithm for efficiently dividing by
seven using bit operators, I don't expect it will work efficiently in
Python. The overhead of using objects will probably outweigh any saving
you might get by using magic tricks, so you should just use division.

It is like using the XOR trick for swapping integers: there's just no
point in doing it in Python except as a trick, because it is slower than
just swapping them:

timeit.Timer("x = x^y; y = x^y; x= x^y", "x, y = 1, 2").repeat() [0.88827300071716309, 0.85192012786865234, 0.81278204917907715]
timeit.Timer("x, y = y, x", "x, y = 1, 2").repeat()

[0.71292495727539062, 0.65545105934143066, 0.68413901329040527]

 

[krypto.wizard]

Its not an homework. I appeared for EA sports interview last month. I
was asked this question and I got it wrong. I have already fidlled
around with the answer but I don't know the correct reasoning behind
it.

Thanks,

 

[John Nagle]

Its not an homework. I appeared for EA sports interview last month. I
was asked this question and I got it wrong. I have already fidlled
around with the answer but I don't know the correct reasoning behind
it.

The answer to that question is that the fastest way to divide
by 7 is to use the divide instruction. You'd have to go down
to a really old 8-bit microprocessor like the Intel 8051 to
find something where bit-twiddling like that pays off.

And no way would this be a win in Python, which is
interpreted.

John Nagle

 

[Paddy]

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.

Not a minus or division operator in sight ;-)

- Paddy.

 

[Ben Finney]

Not a minus or division operator in sight ;-)

I salute you, sir. That's the perfect answer to the boneheaded
constraints of the problem

 

[Paul McGuire]

7

Not a minus or division operator in sight ;-)

- Paddy.

Now I'm confused - was the OP trying to divide by 7 or 2?

-- Paul

 

[John Machin]

The answer to that question is that the fastest way to divide
by 7 is to use the divide instruction. You'd have to go down
to a really old 8-bit microprocessor like the Intel 8051 to
find something where bit-twiddling like that pays off.

Perhaps not that far back. Google "Granlund Montgomery". The technique
got built into gcc.

And no way would this be a win in Python, which is
interpreted.

Agreed.

 

[Marc 'BlackJack' Rintsch]

Now I'm confused - was the OP trying to divide by 7 or 2?

I read it as divide by 7. And the `int.__div__()` Method limits this
somehow -- a more polymorphic approach would be::

import operator
operator.div(14, 7)



Ciao,
Marc 'BlackJack' Rintsch

 

[=?ISO-8859-1?Q?BJ=F6rn_Lindqvist?=]

This is maybe not so efficient but it implements integer division
by 7 for positive integers without - and /.

def div2(num):
return num >> 1

def div4(num):
return num >> 2

def div8(num):
return num >> 3

def mul2(num):
return num << 1

def mul4(num):
return num << 2

def mul7(num):
return mul4(num) + mul2(num) + num

def div7_help(num, lo, hi):
avg = div2(lo + hi)

if avg == lo or avg == hi:
if mul7(hi) == num:
return hi
return lo

avg7 = mul7(avg)
if avg7 > num:
return div7_help(num, lo, avg)
elif avg7 < num:
return div7_help(num, avg, hi)
return avg

def div7(num):
lo = div8(num)
hi = div4(num)

return div7_help(num, lo, hi)

for nr in range(0, 20000):
#print "%d // 7 = %d" % (nr, nr // 7)
#print "div7(%d) = %d" % (nr, div7(nr))
assert nr // 7 == div7(nr)

A somewhat better approach is to convert the recursion to an
interative method. But that is.. um.. left as an exercise.

 

[Nicko]

Its not an homework. I appeared for EA sports interview last month. I
was asked this question and I got it wrong. I have already fidlled
around with the answer but I don't know the correct reasoning behind
it.

In that case, observer that a/b == a * (1/b), and if b is constant you
can compute (1/b) in advance. Since the problem was set by game
programmers I'd hazard that they are OK with relatively limited
precision and the answer that they were looking for was:
a = (b * 04444444445L) >> 32
Note that the constant there is in octal.

Nicko

 

[Krypto]

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

 

[Paul Rubin]

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

Well, not exactly:

[GCC 3.4.2 20041017 (Red Hat 3.4.2-6.fc3)] on linux2
Type "help", "copyright", "credits" or "license" for more information. 98

 

[skip]

Michael> I think it is off by 1 in small numbers, off by a little more
Michael> with large numbers:
...

Sorta makes you think using the DIV instruction in the CPU is the way to
go. ;-)

Skip

 

[Marc 'BlackJack' Rintsch]

The correct answer as told to me by a person is

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

How could it be correct if it uses `-`? You ruled out `-` and `/` in your
first post.

Ciao,
Marc 'BlackJack' Rintsch

 

[Bart Ogryczak]

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

 

[Neil Cerutti]

I think it is off by 1 in small numbers, off by a little more with large
numbers:
... return (N>>3) + ((N-7*(N>>3))>>3)
...
984

Heh, heh. That's reminding of the "fabulous" O(n) Dropsort
algorithm I saw linked from Effbot's blog.

 

[John Machin]

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