1 files changed, 81 insertions, 0 deletions
diff --git a/booth_multiplier.py b/booth_multiplier.py
new file mode 100755
index 0000000..606aee5
--- /dev/null
+++ b/booth_multiplier.py
@@ -0,0 +1,81 @@
+#!/usr/bin/env python3
+with open('input.txt') as f:
+  input_string = f.read().split('\n')
+
+def twos_comp(num, length):
+  if num == 0:
+    return 0
+  num ^= ((1 << length) - 1)
+  return num + 1
+
+def logical_shiftr(num, length, times):
+  for t in range(times):
+    num = (num >> 1) | ((1 << length) & num)
+  return num
+
+def convert_if_twoscomp(num, length):
+  if num & (1 << length - 1):
+    return (-1 * twos_comp(num, length))
+  return num & (1 << length) - 1
+
+def debug(multiplicand_b, multiplier_b, length):
+  sign = 0
+  multiplicand = convert_if_twoscomp(multiplicand_b, length)
+  multiplier = convert_if_twoscomp(multiplier_b, length)
+  
+  result = multiplicand * multiplier
+  result_bin = (twos_comp(result, length * 2), result) [result > 0]
+
+  print("expected result:\t{}\t*\t{}\t=\t{}\t=\t{}".format(multiplicand, multiplier, bin(result_bin), multiplicand * multiplier))
+  #print("booths result:\t\t{}\t*\t{}\t=\t{}".format(bin(multiplicand), bin(multiplier), bin(result_booth)))
+
+  
+def booth(multiplier, multiplicand, length):
+  multiplicand_twos_comp = twos_comp(multiplicand, length)
+  result = multiplier << 1 # extended bit
+  for i in range(length):
+    op = result & 0b11
+    if op == 0b01:
+      result += multiplicand << (length + 1)
+    if op == 0b10:
+      result += multiplicand_twos_comp << (length + 1)
+    result &= (1 << (length * 2) + 1) - 1 # get rid of any overflows
+    result = logical_shiftr(result, length * 2, 1)
+  result = result >> 1
+  return result
+
+def booth_mod(multiplier, multiplicand, length):
+  multiplicand_twos_comp = twos_comp(multiplicand, length)
+  result = multiplier << 1 # extended bit
+  for i in range(int(length / 2)):
+    match result & 0b111:
+      case 0b010 | 0b001: # add
+        result += multiplicand << (length + 1)
+      case 0b011:         # add * 2
+        result += multiplicand << (length + 2) # extra shift is multiplying multiplicand by 2
+      case 0b100:         # sub * 2
+        result += multiplicand_twos_comp << (length + 2)
+      case 0b101 | 0b110: # sub
+        result += multiplicand_twos_comp << (length + 1)
+    result &= (1 << (length * 2) + 1) - 1 # get rid of any overflows
+    result = logical_shiftr(result, length * 2, 2)
+  result = result >> 1
+  return result
+
+
+
+
+for operation in input_string:
+  if operation == '' or operation[0] == '#':
+    continue
+  length = len(operation.split(" ")[0])
+  multiplicand = int(operation.split(" ")[0], 2)
+  multiplier = int(operation.split(" ")[1], 2)
+
+  
+  debug(multiplicand, multiplier, length)
+  result_booth = booth(multiplier, multiplicand, length)
+  result_mod_booth = booth_mod(multiplier, multiplicand, length)
+  print("booths:\t\t\t", bin(result_booth))
+  print("modified booths:\t", bin(result_mod_booth))
+