On Feb 7, 11:05 am, [EMAIL PROTECTED] wrote: > On Feb 6, 4:54 pm, "John Machin" <[EMAIL PROTECTED]> 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 -- http://mail.python.org/mailman/listinfo/python-list
