1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
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))
|
