division by 7 efficiently ???

[Roel Schroeven]

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