division by 7 efficiently ???

[Jesse Chounard]

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:
.... return ((N * 9362) >> 16) + 1
....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]

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.

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

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:
.... 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]

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]

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]

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]

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]

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]

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]

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]

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


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.

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]

(e-mail address removed) 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.

 

[Roel Schroeven]

Roel Schroeven schreef:

(e-mail address removed) schreef:

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.