carry_equations_generator.py

# -*- coding: utf-8 -*-
"""
Created on Fri Jan 30 15:07:02 2015

@author: Richard
"""

import itertools
import sympy

import GenerateTableOutput
import GenerateCarry
import EquationHandler
import ReHandler

from sympy_helper_fns import is_equation


## Parsing and set up

def parse_equations(params):
    '''
        params[0][i] contains all leftsides
        params[1][i] contains all rightsides
    '''
    eqns = []
    variables = {}
    for lhs, rhs in itertools.izip(*params):
        lhs = _parse_expression(lhs, variables)
        rhs = _parse_expression(rhs, variables)
        eqn = sympy.Eq(lhs, rhs)
        eqns.append(eqn)

    return eqns, variables

def _parse_expression(expr, variables):
    ''' Take a list of terms, clean them up and return a sympy expression in terms
        of the global variables '''
    out = 0
    for term in expr:
        if term == '':
            continue
        out += _parse_term(term, variables)
    return out

def _parse_term(term, variables):
    ''' Take a term and clean it, replacing variables '''
    coef = int(ReHandler.get_coefficient(term))
    var = ReHandler.get_variables(term)
    var_instances = []
    for v in var:
        instance = variables.get(v)
        if instance is None:
            instance = sympy.symbols(v)
            variables[v] = instance
        var_instances.append(instance)
    return coef * sympy.prod(var_instances)

def generate_carry_equations(digitsInMultiplicand1, digitsInMultiplicand2, product):
    ''' Generate standard carry equations
        >>> eqns = generate_carry_equations(4, 4, 143)
        >>> for e in eqns: print e
        p1 + q1 == 2*z12 + 1
        p1*q1 + p2 + q2 + z12 == 2*z23 + 4*z24 + 1
        p1*q2 + p2*q1 + z23 + 2 == 2*z34 + 4*z35 + 1
        p1 + p2*q2 + q1 + z24 + z34 == 2*z45 + 4*z46
        p2 + q2 + z35 + z45 == 2*z56 + 4*z57
        z46 + z56 + 1 == 2*z67
        z57 + z67 == 1
    '''
    params = _generate_carry_equations(digitsInMultiplicand1=digitsInMultiplicand1,
                                      digitsInMultiplicand2=digitsInMultiplicand2,
                                      product=product)
    eqns, variables = parse_equations(params)
    return filter(is_equation, eqns)

def _generate_carry_equations(digitsInMultiplicand1, digitsInMultiplicand2, product):
    ''' Generate standard carry equations
        >>> eqns = _generate_carry_equations(4, 4, 143)
        >>> for e in eqns: print e
        [['1', '', '', ''], ['p1', 'q1', '', ''], ['p2', 'p1q1', 'q2', '', 'z12'], ['1', 'p2q1', 'p1q2', '1', 'z23'], ['', 'q1', 'p2q2', 'p1', 'z34', 'z24'], ['', '', 'q2', 'p2', 'z45', 'z35'], ['', '', '', '1', 'z56', 'z46'], ['', '', '', '', 'z67', 'z57']]
        [['1'], ['1', '2z12'], ['1', '2z23', '4z24'], ['1', '2z34', '4z35'], ['0', '2z45', '4z46'], ['0', '2z56', '4z57'], ['0', '2z67'], ['1']]
    '''
    numMultipliers = 2    #eventually this will be dynamically generated by output

    multiplier = []
    multiplication = []
    carry = []

    #digitsInMultiplicand1 will always have the greater number of digits
    if digitsInMultiplicand1 < digitsInMultiplicand2:
        temp = digitsInMultiplicand1
        digitsInMultiplicand1 = digitsInMultiplicand2
        digitsInMultiplicand2 = temp

    binPrime = bin(product)[2:]
    if (digitsInMultiplicand1 + digitsInMultiplicand2) > len(binPrime):
        for i in range (0, ((digitsInMultiplicand1 + digitsInMultiplicand2)-len(binPrime))):
            binPrime = "0" + binPrime

#    print binPrime

    #Generate multipliers based on digits
    #    They take form 1,p2,p1,1 and 1,q2,q1,1
    #    This code will have to be rewritten to support >2 multiplicands
    strP = []
    strQ = []
    for i in range(1,digitsInMultiplicand1-1):
        strP.append("p" + str(i))
    for i in range(1, digitsInMultiplicand2-1):
        strQ.append("q" + str(i))
    strP.append("1")
    strP.insert(0, "1")
    strQ.append("1")
    strQ.insert(0, "1")
    multiplier.append(strP)
    multiplier.append(strQ)

    #Generate intermediary Multiplication row values
    #    This is the result of multiplying p by every bit of q
    for i in strQ:
        temp = []
        for j in strP:
            if i == "1":
                temp.append(j)
            else:
                if j == "1":
                    temp.append(i)
                else:
                    temp.append(j + i)
        multiplication.append(temp)

    #Find Carry row values
    myParams = [digitsInMultiplicand1, digitsInMultiplicand2]
    carry = GenerateCarry.CarryGenerator(myParams)

    #Generate Output
    myParams = [multiplier, multiplication, carry, binPrime]
    formattedCols = GenerateTableOutput.FormatOutput(myParams)
    #print ""

    #Generate Equations
    myParams = [formattedCols, carry]
    eqns = EquationHandler.GenerateEquations(myParams)

    return eqns


if __name__ == "__main__":
    import doctest
    doctest.testmod()