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]

kr***********@gmail.com writes:

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]

kr***********@gmail.com writes:

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.

--
\ "I like to go to art museums and name the untitled paintings. |
`\ 'Boy With Pail'. 'Kitten On Fire'." -- Steven Wright |
_o__) |
Ben Finney

[Steven D'Aprano]

On Wed, 31 Jan 2007 18:42:54 -0800, krypto.wizard 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.

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]
--
Steven D'Aprano

[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,
On Jan 31, 10:01 pm, Ben Finney <[e-mail]>
wrote:

[e-mail] writes:

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.

--
\ "I like to go to art museums and name the untitled paintings. |
`\ 'Boy With Pail'. 'Kitten On Fire'." -- Steven Wright |
_o__) |
Ben Finney

[John Nagle]

kr***********@gmail.com wrote:

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]

On Feb 1, 2:42 am, [e-mail] 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.

>>int.__div__(14,2)

7

>>>

Not a minus or division operator in sight ;-)

- Paddy.

[Ben Finney]

"Paddy" <pa*******@netscape.netwrites:

On Feb 1, 2:42 am, [e-mail] wrote:

How to divide a number by 7 efficiently without using - or / operator.

>int.__div__(14,2)

7

>>

Not a minus or division operator in sight ;-)

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

--
\ "What I resent is that the range of your vision should be the |
`\ limit of my action." -- Henry James |
_o__) |
Ben Finney

[Paul McGuire]

On Jan 31, 11:36 pm, "Paddy" <[e-mail]:

On Feb 1, 2:42 am, [e-mail] 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.

>int.__div__(14,2)

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]

On Feb 1, 2:36 pm, John Nagle <[e-mail]:

[e-mail] wrote:

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.

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]

In <11*********************@a34g2000cwb.googlegroups. com>, Paul McGuire
wrote:

On Jan 31, 11:36 pm, "Paddy" <[e-mail]:

>On Feb 1, 2:42 am, [e-mail] 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.
int.__div__(14,2)

7

Not a minus or division operator in sight ;-)

- Paddy.

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.

--
mvh Björn

[Nicko]

On Feb 1, 3:13 am, [e-mail] wrote:

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]

"Krypto" <kr***********@gmail.comwrites:

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.

>>def f(N): return (N>>3) + ((N-7*(N>>3))>>3)

...

>>f(7)

0

>>f(70)

9

>>f(700)

98

[skip]

MichaelI think it is off by 1 in small numbers, off by a little more
Michaelwith large numbers:
...

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

Skip

[Marc 'BlackJack' Rintsch]

In <11**********************@a75g2000cwd.googlegroups .com>, Krypto wrote:

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]

On Feb 1, 3:42 am, [e-mail] 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))

[Neil Cerutti]

On 2007-02-01, Michael Yanowitz <m.********@kearfott.comwrote:

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

>>>def div7 (N):

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

>>>div7 (70)

9

>>>div7 (77)

10

>>>div7 (700)

98

>>>div7 (7)

0

>>>div7 (10)

1

>>>div7 (14)

1

>>>div7 (21)

2

>>>div7 (700)

98

>>>div7 (7000)

984

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

--
Neil Cerutti
I'm tired of hearing about money, money, money, money, money. I just want to
play the game, drink Pepsi, wear Reebok. --Shaquille O'Neal

[John Machin]

On Feb 2, 11:03 pm, "Bart Ogryczak" <[e-mail]:

On Feb 1, 3:42 am, [e-mail] 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

[Jesse Chounard]

On 31 Jan 2007 19:13:14 -0800, kr***********@gmail.com
<kr***********@gmail.comwrote:

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.

I think this works:

>>def div7 (N):

.... return ((N * 9362) >16) + 1
....

>>div7(7)

1

>>div7(14)

2

>>div7(700)

100

>>div7(70000)

10000

The coolest part about that (whether it works or not) is that it's my
first Python program. I wrote it in C first and had to figure out how
to convert it. :)

Jesse

[John Machin]

On Feb 3, 2:31 am, "Jesse Chounard" <[e-mail]:

On 31 Jan 2007 19:13:14 -0800, [e-mail]

<[e-mail]:

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.

I think this works:

You think wrongly. Inspection reveals that it is obviously incorrect
for N == 0. Trivial testing reveals that it is wrong for about 6 out
of every 7 cases.

>

>def div7 (N):

... return ((N * 9362) >16) + 1
...>>div7(7)
1

>div7(14)

2

>div7(700)

100

>div7(70000)

10000

The coolest part about that (whether it works or not) is that it's my
first Python program. I wrote it in C first and had to figure out how
to convert it. :)

Try testing algorithms with a pencil on the back of an envelope first.

The uncoolest part about that is that your test data is horribly
deficient:

>>for N in xrange(0, 23):

.... a = ((N * 9362) >16) + 1
.... e = N // 7
.... print N, a, e, a == e
....
0 1 0 False
1 1 0 False
2 1 0 False
3 1 0 False
4 1 0 False
5 1 0 False
6 1 0 False
7 1 1 True
8 2 1 False
9 2 1 False
10 2 1 False
11 2 1 False
12 2 1 False
13 2 1 False
14 2 2 True
15 3 2 False
16 3 2 False
17 3 2 False
18 3 2 False
19 3 2 False
20 3 2 False
21 3 3 True
22 4 3 False

HTH,
John

[Bart Ogryczak]

On Feb 1, 2:00 pm, "Nicko" <[e-mail]:

precision and the answer that they were looking for was:
a = (b * 04444444445L) >32
Note that the constant there is in octal.

04444444445L? Shouldn´t it be 04444444444?
Or more generally,
const = (1<<bitPrecision)/7
a = (b * const)>>bitPrecision

[Nicko]

On Feb 2, 4:21 pm, "Bart Ogryczak" <[e-mail]:

On Feb 1, 2:00 pm, "Nicko" <[e-mail]:

precision and the answer that they were looking for was:
a = (b * 04444444445L) >32
Note that the constant there is in octal.

04444444445L? Shouldn´t it be 04444444444?
Or more generally,
const = (1<<bitPrecision)/7
a = (b * const)>>bitPrecision

It's to do with rounding. What you actually need is
ceiling((1<<bitPrecision)/7), rather than floor((1<<bitPrecision)/7).

Nicko

[Nicko]

On Feb 1, 8:25 pm, "Krypto" <[e-mail]:

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

No it doesn't. The above term tends towards N * (9/64), with some
significant rounding errors. 9/64 is a fairly poor (6 bit)
approximation of 1/7 but the principle is the same as the solution I
proposed above.

Nicko

[garrickp]

On Feb 1, 8:25 pm, "Krypto" <[e-mail]:

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

Does anybody else notice that this breaks the spirit of the problem
(regardless of it's accuracy)? 'N-7' uses the subtraction operator,
and is thus an invalid solution for the original question.

Build a recursive function, which uses two arbitrary numbers, say 1
and 100. Check each, times 7, and make sure that your target number,
N, is between them. Increase or decrease your arbitrary numbers as
appropriate. Now pick a random number between those two numbers, and
check it. Figure out which two the answer is between, and then check a
random number in that subset. Continue this, and you will drill down
to the correct answer, by using only *, +, >, and <.

I'll bet money that since this was a programming interview, that it
wasn't a check of your knowledge of obscure formulas, but rather a
check of your lateral thinking and knowledge of programming.

~G

[MRAB]

On Feb 6, 3:29 pm, [e-mail] wrote:

On Feb 1, 8:25 pm, "Krypto" <[e-mail]:

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

Does anybody else notice that this breaks the spirit of the problem
(regardless of it's accuracy)? 'N-7' uses the subtraction operator,
and is thus an invalid solution for the original question.

[snip]
Instead of subtraction you can use complement-and-add: N + ~7 + 1
(that's a tilde '~' not a minus '-').

[John Machin]

On Feb 7, 2:29 am, [e-mail] wrote:

On Feb 1, 8:25 pm, "Krypto" <[e-mail]:

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

Does anybody else notice that this breaks the spirit of the problem
(regardless of it's accuracy)? 'N-7' uses the subtraction operator,
and is thus an invalid solution for the original question.

Build a recursive function, which uses two arbitrary numbers, say 1
and 100.

Recursive? Bzzzt!

Check each, times 7, and make sure that your target number,
N, is between them. Increase or decrease your arbitrary numbers as
appropriate. Now pick a random number between those two numbers, and
check it. Figure out which two the answer is between, and then check a
random number in that subset

Might it not be better to halve the interval at each iteration instead
of calling a random number function? mid = (lo + hi) >1 looks
permitted and cheap to me. Also you don't run the risk of it taking a
very high number of iterations to get a result.

>. Continue this, and you will drill down
to the correct answer, by using only *, +, >, and <.

I'll bet money that since this was a programming interview, that it
wasn't a check of your knowledge of obscure formulas, but rather a
check of your lateral thinking and knowledge of programming.

~G

Did you notice the important word *efficiently* in line 1 of the spec?
Even after ripping out recursion and random numbers, your proposed
solution is still way off the pace.

Cheers,
John

[garrickp]

On Feb 6, 4:54 pm, "John Machin" <[e-mail]:

Recursive? Bzzzt!

I woudl be happy to hear your alternative, which doesn't depend on
language specific tricks. Thus far, all you have suggested is using an
alternative form of the division function, which I would consider to
be outside the spirit of the question (though I have been wrong many
times before).

Might it not be better to halve the interval at each iteration instead
of calling a random number function? mid = (lo + hi) >1 looks
permitted and cheap to me. Also you don't run the risk of it taking a
very high number of iterations to get a result.

I had considered this, but to halve, you need to divide by 2. Using
random, while potentially increasing the number of iterations, removes
the dependency of language tricks and division.

Did you notice the important word *efficiently* in line 1 of the spec?
Even after ripping out recursion and random numbers, your proposed
solution is still way off the pace.

Again, I look forward to reading your solution.

Respectfully, G.

[John Machin]

On Feb 7, 11:05 am, [e-mail] wrote:

On Feb 6, 4:54 pm, "John Machin" <[e-mail]:

Recursive? Bzzzt!

I woudl be happy to hear your alternative, which doesn't depend on
language specific tricks. Thus far, all you have suggested is using an
alternative form of the division function,

Huh? Thus far (in this post) all I've said is (in effect) that IMHO
mentioning recursion is just cause for termination of job interview.

which I would consider to
be outside the spirit of the question (though I have been wrong many
times before).

Might it not be better to halve the interval at each iteration instead
of calling a random number function? mid = (lo + hi) >1 looks
permitted and cheap to me. Also you don't run the risk of it taking a
very high number of iterations to get a result.

I had considered this, but to halve, you need to divide by 2. Using
random, while potentially increasing the number of iterations, removes
the dependency of language tricks and division.

"Potentially increases the number of iterations"? Sorry, the interview
for marketing manager is across the hall. For example if your N must
fit in 16 bits, you could end up with O(2**16) iterations. This may
not show up in acceptance testing. And each iteration involves calling
a random number function. A binary search has a guaranteed upper limit
of O(16). Let's get this in contect: the traditional "long division"
approach takes 16 iterations!

Shifting to divide by a power of 2 is not a "language trick". In any
case any compiler that deserves to be used will replace division by a
power of 2 with a shift.

>

Did you notice the important word *efficiently* in line 1 of the spec?
Even after ripping out recursion and random numbers, your proposed
solution is still way off the pace.

Again, I look forward to reading your solution.

Respectfully, read my other posts in this thread.
The correct answer IMHO is "Semi-decent compilers like gcc will do a
good-enough job of dividing an integer by a constant. Only in
situations like a very high-use library routine where the N is known
to be much smaller than 2**wordsize might it be worthwhile to see if a
bit-bashing approach could generate faster code".

Cheers,
John

[Roel Schroeven]

ga******@gmail.com schreef:

On Feb 6, 4:54 pm, "John Machin" <[e-mail]:

>Recursive? Bzzzt!
Might it not be better to halve the interval at each iteration instead
of calling a random number function? mid = (lo + hi) >1 looks
permitted and cheap to me. Also you don't run the risk of it taking a
very high number of iterations to get a result.

I had considered this, but to halve, you need to divide by 2. Using
random, while potentially increasing the number of iterations, removes
the dependency of language tricks and division.

It's possible to use Fibonacci numbers instead of halving each time;
that requires only addition and subtraction. Unfortunately I forgot
exactly how that works, and I don't have the time to look it up or to
try to reproduce it now. Maybe later.

AFAIK that method is not commonly used since binary computers are very
good at dividing numbers by two, but it would be a good method on
ternary or decimal computers.

--
If I have been able to see further, it was only because I stood
on the shoulders of giants. -- Isaac Newton

Roel Schroeven

[Roel Schroeven]

Roel Schroeven schreef:

ga******@gmail.com schreef:

>I had considered this, but to halve, you need to divide by 2. Using
random, while potentially increasing the number of iterations, removes
the dependency of language tricks and division.

It's possible to use Fibonacci numbers instead of halving each time;
that requires only addition and subtraction. Unfortunately I forgot
exactly how that works, and I don't have the time to look it up or to
try to reproduce it now. Maybe later.

AFAIK that method is not commonly used since binary computers are very
good at dividing numbers by two, but it would be a good method on
ternary or decimal computers.

Responding to myself since I found an explanation in the obvious place:

http://en.wikipedia.org/wiki/Fibonacci_search_technique

It is meant for search in ordered arrays though; I don't think it can be
adapted for searching in mathematic intervals.

--
If I have been able to see further, it was only because I stood
on the shoulders of giants. -- Isaac Newton

Roel Schroeven