division by 7 efficiently ???

[John Machin]

On Feb 7, 11:05 am, garri... at gmail.com wrote:
> On Feb 6, 4:54 pm, "John Machin" <sjmac... at lexicon.net> wrote:
>
> > 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