diff options
Diffstat (limited to 'booth_multiplier.py')
| -rwxr-xr-x | booth_multiplier.py | 83 |
1 files changed, 46 insertions, 37 deletions
diff --git a/booth_multiplier.py b/booth_multiplier.py index dab58d0..6f47b60 100755 --- a/booth_multiplier.py +++ b/booth_multiplier.py @@ -3,34 +3,26 @@ from tabulate import tabulate import matplotlib import matplotlib.pyplot as plt -matplotlib.use("pgf") -matplotlib.rcParams.update({ - "pgf.texsystem": "pdflatex", - 'font.family': 'serif', - 'text.usetex': True, - 'pgf.rcfonts': False, -}) - -with open('input.txt') as f: - input_string = f.read().split('\n') - +# finds the two's compliment of a given number def twos_comp(num, length): if num == 0: return 0 return abs((num ^ ((1 << length) - 1)) + 1) +# arithmaticlly shifts right; divides by 2 def arithmatic_shiftr(num, length, times): for t in range(times): num = (num >> 1) | ((1 << length - 1) & num) return num +# arithmaticlly shifts left; multiplies by 2 def arithmatic_shiftl(num, length): if num & (1 << length - 1): return (num << 1) | (1 << length - 1) else: return (num << 1) & ~(1 << length - 1) - +# only used for debugging function to allow python to natively use two's compliment numbers def twoscomp_to_int(num, length): if num & (1 << length - 1): return (-1 * twos_comp(num, length)) @@ -56,63 +48,70 @@ def booth(multiplier, multiplicand, length): operations = 0 multiplicand_twos_comp = twos_comp(multiplicand, length) result = multiplier << 1 # extended bit - for i in range(length): + for i in range(length): # iteration count is size of one operand op = result & 0b11 if op == 0b01: - operations += 1 + operations += 1 # add upper half by multiplicand result += multiplicand << (length + 1) if op == 0b10: - operations += 1 + operations += 1 # subtract upper half by multiplicand result += multiplicand_twos_comp << (length + 1) result &= (1 << (length * 2) + 1) - 1 # get rid of any overflows result = arithmatic_shiftr(result, (length * 2) + 1, 1) result = result >> 1 return (result, operations) -# TODO clean up def booth_mod(multiplier, multiplicand, length): operations = 0 - multiplicand |= ((1 << length - 1) & multiplicand) << 1 # extend multiplicand sign to prevent overflow when mult/sub by 2 + # extend workspace by *two* bits, MSB to prevent overflow when mult/sub by 2 + multiplicand |= ((1 << length - 1) & multiplicand) << 1 multiplicand_twos_comp = twos_comp(multiplicand, length + 1) - result = multiplier << 1 # extended bit - for i in range(int((length) / 2)): + result = multiplier << 1 + for i in range(int((length) / 2)): # number of iterations is half the op = result & 0b111 - match op: - case 0b010 | 0b001: # add + match op: # take action dependent on last two bits + case 0b010 | 0b001: # add upper half by multiplicand print("add") result += multiplicand << (length + 1) - operations += 1 - case 0b011: # add * 2 + case 0b011: # add upper half by 2x multiplicand print("add * 2") result += arithmatic_shiftl(multiplicand, length + 1) << (length + 1) - operations += 1 - case 0b100: # sub * 2 + case 0b100: # subtract upper half by 2x multiplicand print("sub * 2") result += arithmatic_shiftl(multiplicand_twos_comp, length + 1) << (length + 1) - operations += 1 - case 0b101 | 0b110: # sub + case 0b101 | 0b110: # subtract upper half my multiplicand print("sub ") result += multiplicand_twos_comp << (length + 1) - operations += 1 + if op != 0b111 and op != 0: + operations += 1 result &= (1 << ((length * 2) + 2)) - 1 # get rid of any overflows result = arithmatic_shiftr(result, (length * 2) + 2, 2) - # *barfs on your dog* + # shifts the workspace right by one, while duplicating extra sign bit to second MSB, and clearing the MSB. + # this ensures the result length is 2x the operands. result = ((result | ((1 << ((length * 2) + 2)) >> 1)) & ((1 << ((length * 2) + 1)) - 1)) >> 1 return (result, operations) if __name__ == "__main__": + # set up headers for tables result_headers = ['multiplicand', 'multiplier', 'result (bin)', 'result (hex)'] result_table = [] opcount_headers = ['multiplicand', 'multiplier', 'length', 'booth', 'modified booth'] opcount_table = [] - lengths = [] # for matplotlib plot + lengths = [] ops_booth = [] ops_mod_booth = [] debug_results = [] + # Reads operands from file. + # Each line needs to contain two operands in binary two's compliment form seperated by a space. + # Leading zeros should be appended to convey the length of operands. + # Operands must have the same size. + with open('input.txt') as f: + input_string = f.read().split('\n') + for operation in input_string: if operation == '' or operation[0] == '#': continue @@ -129,16 +128,19 @@ if __name__ == "__main__": ops_mod_booth.append(result_mod_booth[1]) lengths.append(length) - #gather data for report results table + # gather data for report results table result_table.append([bin(multiplicand), bin(multiplier), bin(result_booth[0]), hex(result_booth[0])]) - #gather data for test function to check if simulator is working + # gather data for test function to check if simulator is working debug_results.append([multiplicand, multiplier, result_booth[0], result_mod_booth[0], length]) - #gather data for operation count table + # gather data for operation count table opcount_table.append([bin(multiplicand), bin(multiplier), length, result_booth[1], result_mod_booth[1]]) + # tests validity of results debug(debug_results) + + # generate tables for report print(tabulate(result_table, result_headers, tablefmt="latex")) print(tabulate(opcount_table, opcount_headers)) @@ -149,8 +151,16 @@ if __name__ == "__main__": with open("report/speed_table.tex", "w") as f: f.write(tabulate(opcount_table, opcount_headers, tablefmt="latex_booktabs")) - + # set up plotting + matplotlib.use("pgf") + matplotlib.rcParams.update({ + "pgf.texsystem": "pdflatex", + 'font.family': 'serif', + 'text.usetex': True, + 'pgf.rcfonts': False, + }) + # generate table for operations vs operand length plt.title("Operations vs Operand Length") plt.plot(lengths, ops_booth, '^--m', label='booths algorithim') plt.plot(lengths, ops_mod_booth, 'v--c', label='modified booths algorithim') @@ -159,6 +169,8 @@ if __name__ == "__main__": plt.legend(loc='upper left') plt.savefig('report/performance.pgf') + + # generate table of iterations vs operand length iters_booth = [] iters_mod_booth = [] for length in lengths: @@ -172,6 +184,3 @@ if __name__ == "__main__": plt.gca().set_ylabel("Number of iterations") plt.legend(loc='upper left') plt.savefig('report/iterations.pgf') - - - |