summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorBrett Weiland <brett_weiland@gmail.com>2024-04-06 16:48:27 -0500
committerBrett Weiland <brett_weiland@gmail.com>2024-04-06 16:48:27 -0500
commit53e65de28e1d38c5f2174c519aaab9f7f4195e3b (patch)
treef6c452252f5001c735bc405623ad843c96f1daea
parent8441cfef9b3a0e2c7790c796103fd27150fc1ae4 (diff)
booth and modified booth possibly done
-rwxr-xr-xbooth_multiplier.py81
-rw-r--r--input.txt37
-rw-r--r--rubric.pdfbin0 -> 50314 bytes
3 files changed, 101 insertions, 17 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))
+
diff --git a/input.txt b/input.txt
index 3e4755c..63c7420 100644
--- a/input.txt
+++ b/input.txt
@@ -1,17 +1,20 @@
-1110 1111
-0101 0000
-111111 111111
-101110 110111
-111011 100011
-00011111 01010101
-11010111 01010101
-01010101 11010111
-01110111 00110011
-00000000 01110111
-0101010101 0101010101
-1100111011 1001110000
-1001101110 0101111010
-010101010101 010101010101
-001111100111 000000000000
-101010101010 101010101010
-111001110000 000011111111
+#BEFORE TURNING IN. MAKE SURE THESE ARE RIGHT
+001011 011001
+#1101101 0000111
+#1110 1111
+#0101 0000
+#111111 111111
+#101110 110111
+#111011 100011
+#00011111 01010101
+#11010111 01010101
+#01010101 11010111
+#01110111 00110011
+#00000000 01110111
+#0101010101 0101010101
+#1100111011 1001110000
+#1001101110 0101111010
+#010101010101 010101010101
+#001111100111 000000000000
+#101010101010 101010101010
+#111001110000 000011111111
diff --git a/rubric.pdf b/rubric.pdf
new file mode 100644
index 0000000..466181c
--- /dev/null
+++ b/rubric.pdf
Binary files differ