summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorBrett Weiland <brett_weiland@gmail.com>2024-04-11 00:03:50 -0500
committerBrett Weiland <brett_weiland@gmail.com>2024-04-11 00:03:50 -0500
commitcd17799a11de9a80aa1e1d98129e106083bf14b8 (patch)
tree1ac07919442e0c8d01f43de12289041f191aefc4
parent3d66690b7029037d91fcc524c51d77f68c7fa57e (diff)
just need to add table
-rwxr-xr-xbooth_multiplier.py59
-rw-r--r--pheudo_code0
2 files changed, 43 insertions, 16 deletions
diff --git a/booth_multiplier.py b/booth_multiplier.py
index 58abe8b..afd6710 100755
--- a/booth_multiplier.py
+++ b/booth_multiplier.py
@@ -1,5 +1,6 @@
#!/usr/bin/env python3
from tabulate import tabulate
+import matplotlib.pyplot as plt
with open('input.txt') as f:
input_string = f.read().split('\n')
@@ -21,7 +22,7 @@ def arithmatic_shiftl(num, length):
return (num << 1) & ~(1 << length - 1)
-def convert_if_twoscomp(num, length):
+def twoscomp_to_int(num, length):
if num & (1 << length - 1):
return (-1 * twos_comp(num, length))
return num & (1 << length) - 1
@@ -30,8 +31,8 @@ def debug(results):
headers = ['multiplicand bin', 'multiplier bin', 'multiplicand dec', 'multiplier dec', 'expected bin', 'expected dec', 'booth if correct', 'booth mod if correct']
table = []
for [multiplicand_bin, multiplier_bin, result_booth, result_booth_mod, length] in results:
- multiplicand = convert_if_twoscomp(multiplicand_bin, length)
- multiplier = convert_if_twoscomp(multiplier_bin, length)
+ multiplicand = twoscomp_to_int(multiplicand_bin, length)
+ multiplier = twoscomp_to_int(multiplier_bin, length)
expected = multiplicand * multiplier
expected_bin = (twos_comp(expected, length * 2), expected) [expected > 0]
success_b = [bin(result_booth), "PASS"] [result_booth == expected_bin]
@@ -43,45 +44,58 @@ def debug(results):
def booth(multiplier, multiplicand, length):
+ operations = 0
multiplicand_twos_comp = twos_comp(multiplicand, length)
result = multiplier << 1 # extended bit
for i in range(length):
op = result & 0b11
if op == 0b01:
+ operations += 1
result += multiplicand << (length + 1)
if op == 0b10:
+ operations += 1
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
+ return (result, operations)
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
multiplicand_twos_comp = twos_comp(multiplicand, length + 1)
result = multiplier << 1 # extended bit
- operations = 0
for i in range(int((length) / 2)):
- match result & 0b111:
+ op = result & 0b111
+ match op:
case 0b010 | 0b001: # add
+ print("add")
result += multiplicand << (length + 1)
+ operations += 1
case 0b011: # add * 2
- result += arithmatic_shiftl(multiplicand, length + 1) << (length + 1) # extra shift is multiplying multiplicand by 2
+ print("add * 2")
+ result += arithmatic_shiftl(multiplicand, length + 1) << (length + 1)
+ operations += 1
case 0b100: # sub * 2
- result += arithmatic_shiftl(multiplicand_twos_comp, length + 1) << (length + 1) # extra shift is multiplying multiplicand by 2
+ print("sub * 2")
+ result += arithmatic_shiftl(multiplicand_twos_comp, length + 1) << (length + 1)
+ operations += 1
case 0b101 | 0b110: # sub
+ print("sub ")
result += multiplicand_twos_comp << (length + 1)
+ 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*
result = ((result | ((1 << ((length * 2) + 2)) >> 1)) & ((1 << ((length * 2) + 1)) - 1)) >> 1
- return result
-
-
-
+ return (result, operations)
if __name__ == "__main__":
headers = ['multiplicand', 'multiplier', 'result (bin)', 'result (hex)']
table = []
+ lengths = [] # for matplotlib plot
+ ops_booth = []
+ ops_mod_booth = []
debug_results = []
@@ -95,11 +109,24 @@ if __name__ == "__main__":
result_booth = booth(multiplier, multiplicand, length)
result_mod_booth = booth_mod(multiplier, multiplicand, length)
- table.append([bin(multiplicand), bin(multiplier), bin(result_booth), hex(result_booth)])
- debug_results.append([multiplicand, multiplier, result_booth, result_mod_booth, length])
+
+ # gather data for matplotlib
+ ops_booth.append(result_booth[1])
+ ops_mod_booth.append(result_mod_booth[1])
+ lengths.append(length)
+
+ table.append([bin(multiplicand), bin(multiplier), bin(result_booth[0]), hex(result_booth[0])])
+ debug_results.append([multiplicand, multiplier, result_booth[0], result_mod_booth[0], length])
+
debug(debug_results)
print(tabulate(table, headers))
-
- #generate table
+
+ # generate graph
+ plt.plot(lengths, ops_booth, '^--m', label='booths algorithim')
+ plt.plot(lengths, ops_mod_booth, 'v--c', label='modified booths algorithim')
+ plt.gca().set_xlabel("Length of Operands")
+ plt.gca().set_ylabel("Number of Additions and Subtractions")
+ plt.legend(loc='upper left')
+ plt.show()
diff --git a/pheudo_code b/pheudo_code
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/pheudo_code