'''
algorithms from section 2.5, Rosen's DMA 5th
    by Yue Wang 28.11.2014
'''

'''
Constructing Base b Expansions
O( log base (num) )
'''
def get_expansion(num, base=2) :
    expansion = []
    while num>0 :
        expansion = [num%base] + expansion
        num //= base
    return expansion

'''
Addition of Integers
O(n)
'''
def add(lhs, rhs, base=2) :
    l = get_expansion(lhs,base)
    r = get_expansion(rhs,base)
    size = max(len(l),len(r))
    l = [0] * (size-len(l)) + l
    r = [0] * (size-len(r)) + r
    ret = []
    carry = 0
    for i in reversed(range(size)) :
        digit_sum = l[i] + r[i] + carry
        ret = [digit_sum % base] + ret
        carry = digit_sum//base
    if(carry>0):
        ret = [carry] + ret
    return ret

'''
Multiplying Intergers
O(n)
'''
def multiply(lhs, rhs) :
    l = get_expansion(lhs)
    list_for_ret = []
    for i in range(len(l)) :
        if l[i] :
            list_for_ret += [rhs << (len(l) - i - 1)]
    ret = 0
    for num in list_for_ret :
        ret += num
    return ret

@@ -1015,24 +1015,383 @@
 t += num%0A    return ret%0A
+%0A'''%0AComputing div and mod%0AO(n)%0A@note rhs must be greater than 0%0A'''%0Adef division(lhs, rhs) :%0A    quotient    = 0%0A    remainder   = abs(lhs)%0A    while remainder %3E= rhs :%0A        remainder   -= rhs%0A        quotient    += 1%0A    if lhs%3C0 and remainder%3E0 :%0A        remainder   = rhs - remainder%0A        quotient    = -(quotient+1)%0A    return (quotient,remainder)%0A

add division modified: number.py