# Alfonso Cevallos. March 4 2015.
# Please report any mistakes.
# Rules of the game: do not use Python integers, only bit lists!
# Most functions use ITERATION, as opposed to the RECURSION seen in class. Compare them!

# This file contains the implementation of the following algorithms:
# Leading1 reveals the position of the leading 1, and removes any leading zeros.
# Conversion from a bit-representation of a number to a Python integer
# Sum of two bit strings
# Subtraction of two bit strings
# Simple algorithm for multiplying two numbers
# Karatsuba algorithm for multiplying two numbers
# Hybrid multiplication algorithm: it uses Karatsuba when numbers are big, and the simple algorithm when they are small
# Random bit string generator

# In my tests, Karatsuba is slower than simple multiplication even for 1000 bits.
# At that point the hybrid is roughly 2 times faster than the simple multiplication,
# and the latter 5 times faster than Karatsuba; with the first gap increasing and the second decreasing.
# Have a look at the attached plot.


import math
import os
import random
import time

def Leading1(A):  #Traverse the list starting from most significant bit, until we find the first 1.
    for i in xrange(len(A) - 1, -1, -1):
        if A[i] != 0: return i
        else: A.pop()   #Remove unnecessary zeros on the fly
    return -1

def Intify(A):  # Convert a bit list into a Python integer
    s = 0  # We use this only for checking correctness of our algorithms
    for b in reversed(A):
		s = 2*s + b
    return s

def Rand(n):  # Generate a random bit list with n entries, the most significant bit being 1
    A = []    #Here n is assumed to be an integer, not a list.
    for i in range(n - 1):
        A.append(random.randint(0, 1))
    A.append(1)
    return A

def Add(A, B):  # Add two bit lists
    if Leading1(A) < Leading1(B): A,B = B,A  #swaps the pointers, to ensure  len(A)>=len(B)
    Out = []
    carry = 0
    for i in range(len(A)):
        if i < len(B): h = carry + A[i] + B[i]
        else: h = carry + A[i]
        Out.append(h % 2)
        if h > 1: carry = 1
        else: carry = 0
    if carry == 1: Out.append(1)
    return Out

def Sub(A, B):  # Compute A-B
    if Leading1(A)<Leading1(B): return -1 # remove leading zeros and make sure len(A)>=len(B), else report error
    Out = []
    carry = 0
    for i in range(len(A)):
        if i < len(B): h = A[i] - B[i] - carry
        else: h = A[i] - carry
        Out.append(h % 2)
        if h < 0: carry = 1
        else: carry = 0
    if carry == 1: return -1  # if the last carry is 1, L2 was bigger than L1. Report an error
    Leading1(Out)   # this line removes any leading zeros
    return Out

def SimpleMult(A, B):  # Standard multiplication A * B
    if Leading1(A) < Leading1(B): A,B = B,A # remove leading zeros and ensure len(L1)>=len(L2)
    Out = []
    for b in reversed(B):
        Out.insert(0,0)
        if b==1: Out = Add(Out,A)
    return Out

def KaratsubaMult(A, B): # We compute A*B using the Karatsuba algorithm
    if Leading1(A) < Leading1(B): A,B = B,A  # swap the pointers, to ensure len(a)>=len(b)
    if len(B) == 0: return [0]
    if len(B) == 1: return A

    k = len(A) // 2         # split the lists at this point
    A0 = A[:k]
    A1 = A[k:]
    B0 = B[:k]
    B1 = B[k:]      # we have A*B = (A1*2^k + A0) * (B1*2^k + B0)
    S2 = KaratsubaMult(A1, B1)
    S0 = KaratsubaMult(A0, B0)
    SS = KaratsubaMult(Add(A1, A0), Add(B1, B0))
    S1 = Sub(SS, Add(S2, S0)) # we have A*B = (S2*2^k + S1)*2^k + S0
    return Add(([0]*k + Add(([0]*k + S2), S1)), S0)

def HybridMult(A, B):
# We compute A*B using the Karatsuba algorithm; except if input is smaller than the limit.
    limit = 60
    if Leading1(A) < Leading1(B): A,B = B,A  # swap the pointers, to ensure len(a)>=len(b)
    if len(A) < limit: return SimpleMult(A,B) #Use simple multiplication

    k = len(A) // 2         # split the lists at this point
    A0 = A[:k]
    A1 = A[k:]
    B0 = B[:k]
    B1 = B[k:]      # we have A*B = (A1*2^k + A0) * (B1*2^k + B0)
    S2 = HybridMult(A1, B1)
    S0 = HybridMult(A0, B0)
    SS = HybridMult(Add(A1, A0), Add(B1, B0))
    S1 = Sub(SS, Add(S2, S0)) # we have A*B = (S2*2^k + S1)*2^k + S0
    return Add(([0]*k + Add(([0]*k + S2), S1)), S0)

def TestOperations():

    L1 = [0,1,1,0,1,1,0,1]
    print L1 , Intify(L1), "\n"

    L2 = [1,1,0,0,1]
    print L2 , Intify(L2), "\n"

    L3 = Add(L1,L2)
    print "Sum: ", L3, Intify(L3), "\n"

    L4 = Sub(L1,L2)
    print "Difference: ", L4, Intify(L4), "\n"

    L5 = SimpleMult(L1,L2)
    print "Product: ", L5, Intify(L5), "\n"

def TestKaratsuba():
    # Now, let's generate random integers and print the running time of the three algorithms
    nr_bits = [100, 200, 300, 400, 500, 600, 700, 800, 900] # which string size we want to test
    nr_instances= 10 # how many instances for each string size we want to test

    for i in range(9): #tests

        tot_time_kara=0.0
        tot_time_simple=0.0
        tot_time_hybrid=0.0

        for j in range(nr_instances):
            number1 = Rand(nr_bits[i])
            number2 = Rand(nr_bits[i])
            temp=time.clock()
            prod_kara = KaratsubaMult(number1,number2)
            tot_time_kara=tot_time_kara + time.clock()-temp
            temp=time.clock()
            prod_simple = SimpleMult(number1,number2)
            tot_time_simple=tot_time_simple + time.clock()-temp
            temp=time.clock()
            prod_hybrid = HybridMult(number1,number2)
            tot_time_hybrid=tot_time_hybrid + time.clock()-temp

            if Intify(prod_kara) != Intify(prod_simple) or Intify(prod_kara) != Intify(prod_hybrid):
                print "Error in the computation"

        print "%d instances with %d bits each \n" % (nr_instances,nr_bits[i])
        print "Running time Karatsuba:"
        print tot_time_kara/nr_instances
        print "Running time Simple Multiplication: "
        print tot_time_simple/nr_instances
        print "Running time Hybrid Multiplication: "
        print tot_time_hybrid/nr_instances, "\n"

TestOperations()
TestKaratsuba()