division by 7 efficiently ???

[BJörn Lindqvist]

This is maybe not so efficient :) but it implements integer division
by 7 for positive integers without - and /.

def div2(num):
    return num >> 1

def div4(num):
    return num >> 2

def div8(num):
    return num >> 3

def mul2(num):
    return num << 1

def mul4(num):
    return num << 2

def mul7(num):
    return mul4(num) + mul2(num) + num

def div7_help(num, lo, hi):
    avg = div2(lo + hi)

    if avg == lo or avg == hi:
        if mul7(hi) == num:
            return hi
        return lo

    avg7 = mul7(avg)
    if avg7 > num:
        return div7_help(num, lo, avg)
    elif avg7 < num:
        return div7_help(num, avg, hi)
    return avg

def div7(num):
    lo = div8(num)
    hi = div4(num)

    return div7_help(num, lo, hi)

for nr in range(0, 20000):
    #print "%d // 7 = %d" % (nr, nr // 7)
    #print "div7(%d) = %d" % (nr, div7(nr))
    assert nr // 7 == div7(nr)

A somewhat better approach is to convert the recursion to an
interative method. But that is.. um.. left as an exercise.

-- 
mvh Björn