division by 7 efficiently ???

[John Machin]

On Feb 7, 2:29 am, garri... at gmail.com wrote:
> On Feb 1, 8:25 pm, "Krypto" <krypto.wiz... at gmail.com> wrote:
>
> > 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