forgot sudo code

6 files changed, 286 insertions, 201 deletions

diff --git a/.~lock.project description.24.doc# b/.~lock.project description.24.doc#
index bed60cd..336dba6 100644
--- a/.~lock.project description.24.doc#
+++ b/.~lock.project description.24.doc#
@@ -1 +1 @@
-,indigo,indigo,11.04.2024 20:05,file:///home/indigo/.config/libreoffice/4;
\ No newline at end of file
+,indigo,indigo,12.04.2024 12:10,file:///home/indigo/.config/libreoffice/4;
\ No newline at end of file
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')
-
-  
-
diff --git a/report/report.aux b/report/report.aux
index cba120b..a6d55d4 100644
--- a/report/report.aux
+++ b/report/report.aux
@@ -1,2 +1,3 @@
 \relax 
-\gdef \@abspage@last{5}
+\@writefile{lol}{\contentsline {lstlisting}{../booth\textunderscore multiplier.py}{3}{}\protected@file@percent }
+\gdef \@abspage@last{9}
diff --git a/report/report.log b/report/report.log
index bb9709f..709b23b 100644
--- a/report/report.log
+++ b/report/report.log
@@ -1,4 +1,4 @@
-This is pdfTeX, Version 3.141592653-2.6-1.40.26 (TeX Live 2024/Arch Linux) (preloaded format=pdflatex 2024.4.11)  12 APR 2024 01:08
+This is pdfTeX, Version 3.141592653-2.6-1.40.26 (TeX Live 2024/Arch Linux) (preloaded format=pdflatex 2024.4.11)  12 APR 2024 13:47
 entering extended mode
  restricted \write18 enabled.
  %&-line parsing enabled.
@@ -103,15 +103,65 @@ Package: float 2001/11/08 v1.3d Float enhancements (AL)
 \@float@everytoks=\toks22
 \@floatcapt=\box52
 )
+(/usr/share/texmf-dist/tex/latex/listings/listings.sty
+\lst@mode=\count270
+\lst@gtempboxa=\box53
+\lst@token=\toks23
+\lst@length=\count271
+\lst@currlwidth=\dimen162
+\lst@column=\count272
+\lst@pos=\count273
+\lst@lostspace=\dimen163
+\lst@width=\dimen164
+\lst@newlines=\count274
+\lst@lineno=\count275
+\lst@maxwidth=\dimen165
+
+(/usr/share/texmf-dist/tex/latex/listings/lstpatch.sty
+File: lstpatch.sty 2024/02/21 1.10 (Carsten Heinz)
+)
+(/usr/share/texmf-dist/tex/latex/listings/lstmisc.sty
+File: lstmisc.sty 2024/02/21 1.10 (Carsten Heinz)
+\c@lstnumber=\count276
+\lst@skipnumbers=\count277
+\lst@framebox=\box54
+)
+(/usr/share/texmf-dist/tex/latex/listings/listings.cfg
+File: listings.cfg 2024/02/21 1.10 listings configuration
+))
+Package: listings 2024/02/21 1.10 (Carsten Heinz)
+
+(/usr/share/texmf-dist/tex/latex/xcolor/xcolor.sty
+Package: xcolor 2023/11/15 v3.01 LaTeX color extensions (UK)
+
+(/usr/share/texmf-dist/tex/latex/graphics-cfg/color.cfg
+File: color.cfg 2016/01/02 v1.6 sample color configuration
+)
+Package xcolor Info: Driver file: pdftex.def on input line 274.
+
+(/usr/share/texmf-dist/tex/latex/graphics-def/pdftex.def
+File: pdftex.def 2022/09/22 v1.2b Graphics/color driver for pdftex
+)
+(/usr/share/texmf-dist/tex/latex/graphics/mathcolor.ltx)
+Package xcolor Info: Model `cmy' substituted by `cmy0' on input line 1350.
+Package xcolor Info: Model `hsb' substituted by `rgb' on input line 1354.
+Package xcolor Info: Model `RGB' extended on input line 1366.
+Package xcolor Info: Model `HTML' substituted by `rgb' on input line 1368.
+Package xcolor Info: Model `Hsb' substituted by `hsb' on input line 1369.
+Package xcolor Info: Model `tHsb' substituted by `hsb' on input line 1370.
+Package xcolor Info: Model `HSB' substituted by `hsb' on input line 1371.
+Package xcolor Info: Model `Gray' substituted by `gray' on input line 1372.
+Package xcolor Info: Model `wave' substituted by `hsb' on input line 1373.
+)
 (/usr/share/texmf-dist/tex/latex/pgf/basiclayer/pgf.sty
 (/usr/share/texmf-dist/tex/latex/pgf/utilities/pgfrcs.sty
 (/usr/share/texmf-dist/tex/generic/pgf/utilities/pgfutil-common.tex
-\pgfutil@everybye=\toks23
-\pgfutil@tempdima=\dimen162
-\pgfutil@tempdimb=\dimen163
+\pgfutil@everybye=\toks24
+\pgfutil@tempdima=\dimen166
+\pgfutil@tempdimb=\dimen167
 )
 (/usr/share/texmf-dist/tex/generic/pgf/utilities/pgfutil-latex.def
-\pgfutil@abb=\box53
+\pgfutil@abb=\box55
 )
 (/usr/share/texmf-dist/tex/generic/pgf/utilities/pgfrcs.code.tex
 (/usr/share/texmf-dist/tex/generic/pgf/pgf.revision.tex)
@@ -133,45 +183,42 @@ Package: trig 2021/08/11 v1.11 sin cos tan (DPC)
 File: graphics.cfg 2016/06/04 v1.11 sample graphics configuration
 )
 Package graphics Info: Driver file: pdftex.def on input line 107.
-
-(/usr/share/texmf-dist/tex/latex/graphics-def/pdftex.def
-File: pdftex.def 2022/09/22 v1.2b Graphics/color driver for pdftex
-))
-\Gin@req@height=\dimen164
-\Gin@req@width=\dimen165
+)
+\Gin@req@height=\dimen168
+\Gin@req@width=\dimen169
 )
 (/usr/share/texmf-dist/tex/latex/pgf/systemlayer/pgfsys.sty
 (/usr/share/texmf-dist/tex/generic/pgf/systemlayer/pgfsys.code.tex
 Package: pgfsys 2023-01-15 v3.1.10 (3.1.10)
 
 (/usr/share/texmf-dist/tex/generic/pgf/utilities/pgfkeys.code.tex
-\pgfkeys@pathtoks=\toks24
-\pgfkeys@temptoks=\toks25
+\pgfkeys@pathtoks=\toks25
+\pgfkeys@temptoks=\toks26
 
 (/usr/share/texmf-dist/tex/generic/pgf/utilities/pgfkeyslibraryfiltered.code.te
 x
-\pgfkeys@tmptoks=\toks26
+\pgfkeys@tmptoks=\toks27
 ))
-\pgf@x=\dimen166
-\pgf@y=\dimen167
-\pgf@xa=\dimen168
-\pgf@ya=\dimen169
-\pgf@xb=\dimen170
-\pgf@yb=\dimen171
-\pgf@xc=\dimen172
-\pgf@yc=\dimen173
-\pgf@xd=\dimen174
-\pgf@yd=\dimen175
+\pgf@x=\dimen170
+\pgf@y=\dimen171
+\pgf@xa=\dimen172
+\pgf@ya=\dimen173
+\pgf@xb=\dimen174
+\pgf@yb=\dimen175
+\pgf@xc=\dimen176
+\pgf@yc=\dimen177
+\pgf@xd=\dimen178
+\pgf@yd=\dimen179
 \w@pgf@writea=\write3
 \r@pgf@reada=\read2
-\c@pgf@counta=\count270
-\c@pgf@countb=\count271
-\c@pgf@countc=\count272
-\c@pgf@countd=\count273
-\t@pgf@toka=\toks27
-\t@pgf@tokb=\toks28
-\t@pgf@tokc=\toks29
-\pgf@sys@id@count=\count274
+\c@pgf@counta=\count278
+\c@pgf@countb=\count279
+\c@pgf@countc=\count280
+\c@pgf@countd=\count281
+\t@pgf@toka=\toks28
+\t@pgf@tokb=\toks29
+\t@pgf@tokc=\toks30
+\pgf@sys@id@count=\count282
  (/usr/share/texmf-dist/tex/generic/pgf/systemlayer/pgf.cfg
 File: pgf.cfg 2023-01-15 v3.1.10 (3.1.10)
 )
@@ -185,43 +232,24 @@ File: pgfsys-common-pdf.def 2023-01-15 v3.1.10 (3.1.10)
 )))
 (/usr/share/texmf-dist/tex/generic/pgf/systemlayer/pgfsyssoftpath.code.tex
 File: pgfsyssoftpath.code.tex 2023-01-15 v3.1.10 (3.1.10)
-\pgfsyssoftpath@smallbuffer@items=\count275
-\pgfsyssoftpath@bigbuffer@items=\count276
+\pgfsyssoftpath@smallbuffer@items=\count283
+\pgfsyssoftpath@bigbuffer@items=\count284
 )
 (/usr/share/texmf-dist/tex/generic/pgf/systemlayer/pgfsysprotocol.code.tex
 File: pgfsysprotocol.code.tex 2023-01-15 v3.1.10 (3.1.10)
 ))
-(/usr/share/texmf-dist/tex/latex/xcolor/xcolor.sty
-Package: xcolor 2023/11/15 v3.01 LaTeX color extensions (UK)
-
-(/usr/share/texmf-dist/tex/latex/graphics-cfg/color.cfg
-File: color.cfg 2016/01/02 v1.6 sample color configuration
-)
-Package xcolor Info: Driver file: pdftex.def on input line 274.
-
-(/usr/share/texmf-dist/tex/latex/graphics/mathcolor.ltx)
-Package xcolor Info: Model `cmy' substituted by `cmy0' on input line 1350.
-Package xcolor Info: Model `hsb' substituted by `rgb' on input line 1354.
-Package xcolor Info: Model `RGB' extended on input line 1366.
-Package xcolor Info: Model `HTML' substituted by `rgb' on input line 1368.
-Package xcolor Info: Model `Hsb' substituted by `hsb' on input line 1369.
-Package xcolor Info: Model `tHsb' substituted by `hsb' on input line 1370.
-Package xcolor Info: Model `HSB' substituted by `hsb' on input line 1371.
-Package xcolor Info: Model `Gray' substituted by `gray' on input line 1372.
-Package xcolor Info: Model `wave' substituted by `hsb' on input line 1373.
-)
 (/usr/share/texmf-dist/tex/generic/pgf/basiclayer/pgfcore.code.tex
 Package: pgfcore 2023-01-15 v3.1.10 (3.1.10)
 
 (/usr/share/texmf-dist/tex/generic/pgf/math/pgfmath.code.tex
 (/usr/share/texmf-dist/tex/generic/pgf/math/pgfmathutil.code.tex)
 (/usr/share/texmf-dist/tex/generic/pgf/math/pgfmathparser.code.tex
-\pgfmath@dimen=\dimen176
-\pgfmath@count=\count277
-\pgfmath@box=\box54
-\pgfmath@toks=\toks30
-\pgfmath@stack@operand=\toks31
-\pgfmath@stack@operation=\toks32
+\pgfmath@dimen=\dimen180
+\pgfmath@count=\count285
+\pgfmath@box=\box56
+\pgfmath@toks=\toks31
+\pgfmath@stack@operand=\toks32
+\pgfmath@stack@operation=\toks33
 )
 (/usr/share/texmf-dist/tex/generic/pgf/math/pgfmathfunctions.code.tex)
 (/usr/share/texmf-dist/tex/generic/pgf/math/pgfmathfunctions.basic.code.tex)
@@ -235,25 +263,25 @@ x) (/usr/share/texmf-dist/tex/generic/pgf/math/pgfmathfunctions.base.code.tex)
 (/usr/share/texmf-dist/tex/generic/pgf/math/pgfmathfunctions.integerarithmetics
 .code.tex) (/usr/share/texmf-dist/tex/generic/pgf/math/pgfmathcalc.code.tex)
 (/usr/share/texmf-dist/tex/generic/pgf/math/pgfmathfloat.code.tex
-\c@pgfmathroundto@lastzeros=\count278
+\c@pgfmathroundto@lastzeros=\count286
 ))
 (/usr/share/texmf-dist/tex/generic/pgf/math/pgfint.code.tex)
 (/usr/share/texmf-dist/tex/generic/pgf/basiclayer/pgfcorepoints.code.tex
 File: pgfcorepoints.code.tex 2023-01-15 v3.1.10 (3.1.10)
-\pgf@picminx=\dimen177
-\pgf@picmaxx=\dimen178
-\pgf@picminy=\dimen179
-\pgf@picmaxy=\dimen180
-\pgf@pathminx=\dimen181
-\pgf@pathmaxx=\dimen182
-\pgf@pathminy=\dimen183
-\pgf@pathmaxy=\dimen184
-\pgf@xx=\dimen185
-\pgf@xy=\dimen186
-\pgf@yx=\dimen187
-\pgf@yy=\dimen188
-\pgf@zx=\dimen189
-\pgf@zy=\dimen190
+\pgf@picminx=\dimen181
+\pgf@picmaxx=\dimen182
+\pgf@picminy=\dimen183
+\pgf@picmaxy=\dimen184
+\pgf@pathminx=\dimen185
+\pgf@pathmaxx=\dimen186
+\pgf@pathminy=\dimen187
+\pgf@pathmaxy=\dimen188
+\pgf@xx=\dimen189
+\pgf@xy=\dimen190
+\pgf@yx=\dimen191
+\pgf@yy=\dimen192
+\pgf@zx=\dimen193
+\pgf@zy=\dimen194
 LaTeX Font Info:    Trying to load font information for OT1+qpl on input line 9
 26.
 
@@ -262,30 +290,30 @@ File: ot1qpl.fd 2009/09/25 v1.2 font definition file for OT1/qpl
 ))
 (/usr/share/texmf-dist/tex/generic/pgf/basiclayer/pgfcorepathconstruct.code.tex
 File: pgfcorepathconstruct.code.tex 2023-01-15 v3.1.10 (3.1.10)
-\pgf@path@lastx=\dimen191
-\pgf@path@lasty=\dimen192
+\pgf@path@lastx=\dimen195
+\pgf@path@lasty=\dimen196
 ) (/usr/share/texmf-dist/tex/generic/pgf/basiclayer/pgfcorepathusage.code.tex
 File: pgfcorepathusage.code.tex 2023-01-15 v3.1.10 (3.1.10)
-\pgf@shorten@end@additional=\dimen193
-\pgf@shorten@start@additional=\dimen194
+\pgf@shorten@end@additional=\dimen197
+\pgf@shorten@start@additional=\dimen198
 )
 (/usr/share/texmf-dist/tex/generic/pgf/basiclayer/pgfcorescopes.code.tex
 File: pgfcorescopes.code.tex 2023-01-15 v3.1.10 (3.1.10)
-\pgfpic=\box55
-\pgf@hbox=\box56
-\pgf@layerbox@main=\box57
-\pgf@picture@serial@count=\count279
+\pgfpic=\box57
+\pgf@hbox=\box58
+\pgf@layerbox@main=\box59
+\pgf@picture@serial@count=\count287
 )
 (/usr/share/texmf-dist/tex/generic/pgf/basiclayer/pgfcoregraphicstate.code.tex
 File: pgfcoregraphicstate.code.tex 2023-01-15 v3.1.10 (3.1.10)
-\pgflinewidth=\dimen195
+\pgflinewidth=\dimen199
 )
 (/usr/share/texmf-dist/tex/generic/pgf/basiclayer/pgfcoretransformations.code.t
 ex
 File: pgfcoretransformations.code.tex 2023-01-15 v3.1.10 (3.1.10)
-\pgf@pt@x=\dimen196
-\pgf@pt@y=\dimen197
-\pgf@pt@temp=\dimen198
+\pgf@pt@x=\dimen256
+\pgf@pt@y=\dimen257
+\pgf@pt@temp=\dimen258
 ) (/usr/share/texmf-dist/tex/generic/pgf/basiclayer/pgfcorequick.code.tex
 File: pgfcorequick.code.tex 2023-01-15 v3.1.10 (3.1.10)
 )
@@ -297,20 +325,20 @@ x
 File: pgfcorepathprocessing.code.tex 2023-01-15 v3.1.10 (3.1.10)
 ) (/usr/share/texmf-dist/tex/generic/pgf/basiclayer/pgfcorearrows.code.tex
 File: pgfcorearrows.code.tex 2023-01-15 v3.1.10 (3.1.10)
-\pgfarrowsep=\dimen199
+\pgfarrowsep=\dimen259
 )
 (/usr/share/texmf-dist/tex/generic/pgf/basiclayer/pgfcoreshade.code.tex
 File: pgfcoreshade.code.tex 2023-01-15 v3.1.10 (3.1.10)
-\pgf@max=\dimen256
-\pgf@sys@shading@range@num=\count280
-\pgf@shadingcount=\count281
+\pgf@max=\dimen260
+\pgf@sys@shading@range@num=\count288
+\pgf@shadingcount=\count289
 )
 (/usr/share/texmf-dist/tex/generic/pgf/basiclayer/pgfcoreimage.code.tex
 File: pgfcoreimage.code.tex 2023-01-15 v3.1.10 (3.1.10)
 )
 (/usr/share/texmf-dist/tex/generic/pgf/basiclayer/pgfcoreexternal.code.tex
 File: pgfcoreexternal.code.tex 2023-01-15 v3.1.10 (3.1.10)
-\pgfexternal@startupbox=\box58
+\pgfexternal@startupbox=\box60
 )
 (/usr/share/texmf-dist/tex/generic/pgf/basiclayer/pgfcorelayers.code.tex
 File: pgfcorelayers.code.tex 2023-01-15 v3.1.10 (3.1.10)
@@ -325,40 +353,40 @@ File: pgfcorerdf.code.tex 2023-01-15 v3.1.10 (3.1.10)
 )))
 (/usr/share/texmf-dist/tex/generic/pgf/modules/pgfmoduleshapes.code.tex
 File: pgfmoduleshapes.code.tex 2023-01-15 v3.1.10 (3.1.10)
-\pgfnodeparttextbox=\box59
+\pgfnodeparttextbox=\box61
 )
 (/usr/share/texmf-dist/tex/generic/pgf/modules/pgfmoduleplot.code.tex
 File: pgfmoduleplot.code.tex 2023-01-15 v3.1.10 (3.1.10)
 )
 (/usr/share/texmf-dist/tex/latex/pgf/compatibility/pgfcomp-version-0-65.sty
 Package: pgfcomp-version-0-65 2023-01-15 v3.1.10 (3.1.10)
-\pgf@nodesepstart=\dimen257
-\pgf@nodesepend=\dimen258
+\pgf@nodesepstart=\dimen261
+\pgf@nodesepend=\dimen262
 )
 (/usr/share/texmf-dist/tex/latex/pgf/compatibility/pgfcomp-version-1-18.sty
 Package: pgfcomp-version-1-18 2023-01-15 v3.1.10 (3.1.10)
 ))
 (/usr/share/texmf-dist/tex/latex/l3backend/l3backend-pdftex.def
 File: l3backend-pdftex.def 2024-02-20 L3 backend support: PDF output (pdfTeX)
-\l__color_backend_stack_int=\count282
-\l__pdf_internal_box=\box60
+\l__color_backend_stack_int=\count290
+\l__pdf_internal_box=\box62
 ) (./report.aux)
 \openout1 = `report.aux'.
 
-LaTeX Font Info:    Checking defaults for OML/cmm/m/it on input line 31.
-LaTeX Font Info:    ... okay on input line 31.
-LaTeX Font Info:    Checking defaults for OMS/cmsy/m/n on input line 31.
-LaTeX Font Info:    ... okay on input line 31.
-LaTeX Font Info:    Checking defaults for OT1/cmr/m/n on input line 31.
-LaTeX Font Info:    ... okay on input line 31.
-LaTeX Font Info:    Checking defaults for T1/cmr/m/n on input line 31.
-LaTeX Font Info:    ... okay on input line 31.
-LaTeX Font Info:    Checking defaults for TS1/cmr/m/n on input line 31.
-LaTeX Font Info:    ... okay on input line 31.
-LaTeX Font Info:    Checking defaults for OMX/cmex/m/n on input line 31.
-LaTeX Font Info:    ... okay on input line 31.
-LaTeX Font Info:    Checking defaults for U/cmr/m/n on input line 31.
-LaTeX Font Info:    ... okay on input line 31.
+LaTeX Font Info:    Checking defaults for OML/cmm/m/it on input line 33.
+LaTeX Font Info:    ... okay on input line 33.
+LaTeX Font Info:    Checking defaults for OMS/cmsy/m/n on input line 33.
+LaTeX Font Info:    ... okay on input line 33.
+LaTeX Font Info:    Checking defaults for OT1/cmr/m/n on input line 33.
+LaTeX Font Info:    ... okay on input line 33.
+LaTeX Font Info:    Checking defaults for T1/cmr/m/n on input line 33.
+LaTeX Font Info:    ... okay on input line 33.
+LaTeX Font Info:    Checking defaults for TS1/cmr/m/n on input line 33.
+LaTeX Font Info:    ... okay on input line 33.
+LaTeX Font Info:    Checking defaults for OMX/cmex/m/n on input line 33.
+LaTeX Font Info:    ... okay on input line 33.
+LaTeX Font Info:    Checking defaults for U/cmr/m/n on input line 33.
+LaTeX Font Info:    ... okay on input line 33.
 *geometry* driver: auto-detecting
 *geometry* detected driver: pdftex
 *geometry* verbose mode - [ preamble ] result:
@@ -393,19 +421,20 @@ LaTeX Font Info:    ... okay on input line 31.
 * \@reversemarginfalse
 * (1in=72.27pt=25.4mm, 1cm=28.453pt)
 
+\c@lstlisting=\count291
 (/usr/share/texmf-dist/tex/context/base/mkii/supp-pdf.mkii
 [Loading MPS to PDF converter (version 2006.09.02).]
-\scratchcounter=\count283
-\scratchdimen=\dimen259
-\scratchbox=\box61
-\nofMPsegments=\count284
-\nofMParguments=\count285
-\everyMPshowfont=\toks33
-\MPscratchCnt=\count286
-\MPscratchDim=\dimen260
-\MPnumerator=\count287
-\makeMPintoPDFobject=\count288
-\everyMPtoPDFconversion=\toks34
+\scratchcounter=\count292
+\scratchdimen=\dimen263
+\scratchbox=\box63
+\nofMPsegments=\count293
+\nofMParguments=\count294
+\everyMPshowfont=\toks34
+\MPscratchCnt=\count295
+\MPscratchDim=\dimen264
+\MPnumerator=\count296
+\makeMPintoPDFobject=\count297
+\everyMPtoPDFconversion=\toks35
 ) (/usr/share/texmf-dist/tex/latex/epstopdf-pkg/epstopdf-base.sty
 Package: epstopdf-base 2020-01-24 v2.11 Base part for package epstopdf
 Package epstopdf-base Info: Redefining graphics rule for `.eps' on input line 4
@@ -416,67 +445,71 @@ File: epstopdf-sys.cfg 2010/07/13 v1.3 Configuration of (r)epstopdf for TeX Liv
 e
 ))
 LaTeX Font Info:    Trying to load font information for OT1+phv on input line 3
-2.
+4.
 
 (/usr/share/texmf-dist/tex/latex/psnfss/ot1phv.fd
 File: ot1phv.fd 2020/03/25 scalable font definitions for OT1/phv.
 )
 LaTeX Font Info:    External font `cmex10' loaded for size
-(Font)              <14.4> on input line 32.
+(Font)              <14.4> on input line 34.
 LaTeX Font Info:    External font `cmex10' loaded for size
-(Font)              <7> on input line 32.
+(Font)              <7> on input line 34.
 LaTeX Font Info:    External font `cmex10' loaded for size
-(Font)              <12> on input line 42.
+(Font)              <12> on input line 44.
 LaTeX Font Info:    External font `cmex10' loaded for size
-(Font)              <8> on input line 42.
+(Font)              <8> on input line 44.
 LaTeX Font Info:    External font `cmex10' loaded for size
-(Font)              <6> on input line 42.
+(Font)              <6> on input line 44.
+ [1
 
-Underfull \hbox (badness 10000) in paragraph at lines 53--54
+{/var/lib/texmf/fonts/map/pdftex/updmap/pdftex.map}{/usr/share/texmf-dist/fonts
+/enc/dvips/base/8r.enc}{/usr/share/texmf-dist/fonts/enc/dvips/tex-gyre/q-rm.enc
+}]
+Underfull \hbox (badness 10000) in paragraph at lines 55--56
 
  []
 
-[1
-
-{/var/lib/texmf/fonts/map/pdftex/updmap/pdftex.map}{/usr/share/texmf-dist/fonts
-/enc/dvips/base/8r.enc}{/usr/share/texmf-dist/fonts/enc/dvips/tex-gyre/q-rm.enc
-}] [2] (./performance.pgf
+[2] (/usr/share/texmf-dist/tex/latex/listings/lstlang1.sty
+File: lstlang1.sty 2024/02/21 1.10 listings language file
+)
+(../booth_multiplier.py [3] [4] [5] [6]) (./performance.pgf
 LaTeX Font Info:    External font `cmex10' loaded for size
 (Font)              <5> on input line 90.
 )
-Overfull \hbox (9.55966pt too wide) in paragraph at lines 865--82
+Overfull \hbox (9.55966pt too wide) in paragraph at lines 865--126
  [] 
  []
 
 (./iterations.pgf)
-Overfull \hbox (9.55966pt too wide) in paragraph at lines 834--83
+Overfull \hbox (9.55966pt too wide) in paragraph at lines 834--127
  [][] 
  []
 
-(./speed_table.tex [3]) (./result_table.tex) [4] [5] (./report.aux)
+(./speed_table.tex [7]) (./result_table.tex) [8] [9] (./report.aux)
  ***********
 LaTeX2e <2023-11-01> patch level 1
 L3 programming layer <2024-02-20>
  ***********
  ) 
 Here is how much of TeX's memory you used:
- 10639 strings out of 476076
- 208728 string characters out of 5793775
- 1944187 words of memory out of 5000000
- 32537 multiletter control sequences out of 15000+600000
- 589562 words of font info for 59 fonts, out of 8000000 for 9000
+ 12527 strings out of 476076
+ 233580 string characters out of 5793775
+ 2369187 words of memory out of 5000000
+ 34403 multiletter control sequences out of 15000+600000
+ 592840 words of font info for 62 fonts, out of 8000000 for 9000
  14 hyphenation exceptions out of 8191
- 87i,10n,93p,943b,448s stack positions out of 10000i,1000n,20000p,200000b,200000s
+ 87i,10n,93p,951b,1884s stack positions out of 10000i,1000n,20000p,200000b,200000s
 </usr/share/texmf-dist/fonts/type1/public/amsfonts/cm/cmr10.pfb></usr/share/t
 exmf-dist/fonts/type1/public/amsfonts/cm/cmr12.pfb></usr/share/texmf-dist/fonts
 /type1/public/amsfonts/cm/cmsy10.pfb></usr/share/texmf-dist/fonts/type1/public/
-tex-gyre/qplb.pfb></usr/share/texmf-dist/fonts/type1/public/tex-gyre/qplr.pfb><
-/usr/share/texmf-dist/fonts/type1/public/tex-gyre/qplri.pfb></usr/share/texmf-d
-ist/fonts/type1/urw/helvetic/uhvr8a.pfb>
-Output written on report.pdf (5 pages, 185893 bytes).
+amsfonts/cm/cmtt10.pfb></usr/share/texmf-dist/fonts/type1/public/tex-gyre/qplb.
+pfb></usr/share/texmf-dist/fonts/type1/public/tex-gyre/qplr.pfb></usr/share/tex
+mf-dist/fonts/type1/public/tex-gyre/qplri.pfb></usr/share/texmf-dist/fonts/type
+1/urw/helvetic/uhvr8a.pfb>
+Output written on report.pdf (9 pages, 222007 bytes).
 PDF statistics:
- 60 PDF objects out of 1000 (max. 8388607)
- 38 compressed objects within 1 object stream
+ 79 PDF objects out of 1000 (max. 8388607)
+ 51 compressed objects within 1 object stream
  0 named destinations out of 1000 (max. 500000)
  13 words of extra memory for PDF output out of 10000 (max. 10000000)
 
diff --git a/report/report.pdf b/report/report.pdf
index 57a9aae..0594044 100644
--- a/report/report.pdf
+++ b/report/report.pdf
diff --git a/report/report.tex b/report/report.tex
index 6895f89..700585f 100644
--- a/report/report.tex
+++ b/report/report.tex
@@ -6,6 +6,8 @@
 \usepackage[utf8]{inputenc}
 \usepackage{booktabs}
 \usepackage{float}
+\usepackage{listings}
+\usepackage{xcolor}
 
 \usepackage{pgf}
 
@@ -31,12 +33,12 @@ Analyzing Performance of Booth’s Algorithm and Modified Booth’s Algorithm}
 \begin{document}
 \maketitle
 \begin{abstract}
-In this paper, the performance of Booth’s Algorithm is compared to modified Booth's Algorithm. Each multiplier is simulated in Python, and performance is observed by counting the number of add and subtract operations for various inputs. Results are analyzed and discussed to highlight the potential tradeoffs to consider when deciding how hardware multiplication is implimented.
+In this paper, the performance of Booth’s Algorithm is compared to modified Booth's Algorithm. Each multiplier is simulated in Python, and performance is observed by counting the number of add and subtract operations for inputs of various lengths. Results are analyzed and discussed to highlight the potential tradeoffs one should consider when deciding what multiplier is to be used.
 \end{abstract}
 \section*{Introduction}
-Multiplication is among the most time consuming mathematical operations for processors. In many applications, the time it takes to multiply dramatically influences the speed of the program. Applications of digital signal processing (such as audio modification and image processing) require constant multiply and accumulate operations for functions such as fast fourier transformations and convolutions. Other applications are heavily dependent on multiplying large matrices, such as machine learning, 3D graphics and data analysis. In such scenarios, the speed of multiplication is vital. Consequently, most modern processors implement hardware multiplication. However, not all multiplication circuits are equal; there is often a stark contrast between performance and hardware complexity. To further complicate things, multiplication circuits perform differently depending on what numbers are being multiplied.
-\section*{Algorithm Description and Simulation}
-Booth's algorithim computes the product of two signed numbers in two's compliment format. To avoid overflow, the result is placed into a register two times the size of the operands (or two registers the size of a single operand). Additionally, the algorithim must work with a space that is exended one bit more then the result. For the purpose of brevity, the result register and extra bit will be refered to as the workspace, as the algorithim will use this space for its computations. First, the multiplier is placed into the workspace and shifted left by 1. From there, an operation is performed based off the last two bits, as shown by the following table:
+Multiplication is among the most time consuming mathematical operations for processors. In many applications, the time it takes to multiply dramatically influences the speed of the program. Applications of digital signal processing (such as audio modification and image processing) require constant multiply and accumulate operations for functions such as fast fourier transformations and convolutions. Other applications are heavily dependent on multiplying large matrices, such as machine learning, 3D graphics and data analysis. In such scenarios, the speed of multiplication is vital. Consequently, most modern processors implement hardware multiplication. However, not all hardware multiplication schemes are equal; there is often a stark contrast between performance and hardware complexity. To further complicate things, multiplication circuits perform differently depending on what numbers are being multiplied.
+\section*{Algorithm Description}
+Booth's algorithim computes the product of two signed numbers in two's compliment format. To avoid overflow, the result is placed into a register two times the size of the operands (or two registers the size of a single operand). Additionally, the algorithim must work with a space that is exended one bit more then the result. For the purpose of brevity, the result register and extra bit will be refered to as the workspace, as the algorithim uses this space for its computations. First, the multiplier is placed into the workspace and shifted left by 1. From there, the multiplier is used to either add or subtract from the upper half of the workspace. The specific action is dependent on the last two bits of the workspace.
 \begin{table}[H]
   \centering
 \begin{tabular}{lll}
@@ -70,14 +72,56 @@ Bit 2 & Bit 1 & Bit 0 & Action \\
 \bottomrule
 \end{tabular}
 \end{table}
-Because some operations require multiplying the multiplicand by 2, an extra bit is added to the most significant side of the workspace to avoid overflow. After each iteration, the result is arithmaticlly shifted right twice. The number of iterations is only half of the length of the operands. After all iterations, the workspace is shifted right once, and the second most significant bit is set to the first most significant bit as the result register does not include the extra bit.\\
-The purpose of this paper is to analyze and compare the peformance of these two algorithms for various operand lengths and values. As such, all arithmatic bitwise operations had to account for the length of operand sizes. Take for example, the arithmatic shift right functions:
-\begin{center}
-  put phseudo code here
-\end{center}
-Additionally, after each iteration, the bits more significant then the workspace length had to be erased (the bitwise functions purposefully do not account for this). 
-\newpage
-\section*{Results}
+Because some operations require multiplying the multiplicand by 2, an extra bit is added to the most significant side of the workspace to avoid overflow. After each iteration, the result is arithmaticlly shifted right twice. The number of iterations is only half of the length of the operands. After all iterations, the workspace is shifted right once, and the second most significant bit is set to the first most significant bit as the result register does not include the extra bit.
+\par
+\section*{Simulation Implimentation}
+Both algorithims were simulated in Python in attempts to utalize its high level nature for rapid development. The table for Booth's algorithim was preformed with a simple if-then loop, while a switch case was used in modified booth's algorithim. Simple integers were used to represent registers. 
+\par
+One objective of this paper is to analyze and compare the peformance of these two algorithms for various operand lengths. As such, the length of operands had to be constantly accounted for. Aritmatic bitwise operations, including finding two's compliment, were all implimented using functions that took length as an input. Further more, extra bits were cleared after each iteration.
+\par
+To track down issues and test the validity of the multipliers, a debug function was written. To allow Python to natively work with the operands, each value is calculated from its two's compliment format. The converted numbers are then multiplied, and the result is compared to both Booth's Algorithim and Modified Booth's Algorithim. To ensure that the debugging function itself doesn't malfunction, all converted operands and expected results are put into a single large table for checking. The exported version of this table can be seen in table X. % TODO
+\section*{Analysis}
+Modified Booth's algorithim only requires half the iterations as Booth's algorithim. As such, it can be expected that the benifit of modified Booth's algorithim increases two fold with bit length. This can be shown by comparing the two curves in figure X. 
+\par
+Despite this, the nature of both algorithims dictate that modified booth's algorithim is not explicitly faster. Iteration count translates to the \textit{maxiumum} number of additions and subtractions. Figure X shows the performance of the two algorithims given different input lengths, while table x shows the actual data made to generate the plot. There are some interesting things to note. When operands contain repeating zeros or ones, both operations preform similarly, as only shifting is required. Operands containing entirely ones or zeros result in idential preformance. On the contrary, alternating bits within operands demonstrate where the two algorithims differ, as almost no bits can be skipped over. Operands made entirely of alternating bits result in the maximum performance diffrence, in which modified booth's algorithim is potentially two times faster.
+\par
+All of this needs to be considered when designing an ALU. Modified booth's algorithim may improve speed, but requires substantially more hardware to impliment. One must consider if die space is to be allocated to optimize multiplication. In many applications, fast multiplication is unnessesary; many early single-chip processors and microcontrollers didn't impliment multiplication, as they were intended for simple embeded applications.
+\section*{Conclusion}
+Hardware multipliers can help accellerate applications in which multiplication is frequent. When implimenting hardware multipliers, it's important to consider the advantages and disadvantages of various multiplier schemes. Modified Booth's algorithim gives diminishing returns for smaller operands and requires significantly more logic. In applications that depend heavily on fast multiplication of large numbers, modified booth's algorithim is optimal.
+% mba generally but not always faster 
+% application should be considered
+% 
+
+\section*{Appendix}
+\definecolor{codegreen}{rgb}{0,0.6,0}
+\definecolor{codegray}{rgb}{0.5,0.5,0.5}
+\definecolor{codepurple}{rgb}{0.58,0,0.82}
+\definecolor{backcolour}{rgb}{0.95,0.95,0.92}
+
+\lstdefinestyle{mystyle}{
+    backgroundcolor=\color{backcolour},
+    commentstyle=\color{codegreen},
+    keywordstyle=\color{magenta},
+    numberstyle=\tiny\color{codegray},
+    stringstyle=\color{codepurple},
+    basicstyle=\ttfamily\footnotesize,
+    breakatwhitespace=false,
+    breaklines=true,
+    captionpos=b,
+    keepspaces=true,
+    numbers=left,
+    numbersep=5pt,
+    showspaces=false,
+    showstringspaces=false,
+    showtabs=false,
+    tabsize=2
+}
+
+\lstset{style=mystyle}
+\lstinputlisting[language=Python]{../booth_multiplier.py}
+% efficiency gets comparitively better over length
+% not much for the smaller operands
+% lots of repeated 1s and 0s very good for both algorithims
 \begin{center}
   \input{performance.pgf}\\
   \input{iterations.pgf}\\
@@ -85,7 +129,5 @@ Additionally, after each iteration, the bits more significant then the workspace
   \input{result_table.tex}\\
 \end{center}
     
-\section*{Analysis}
-\section*{Conclusion}
 \end{document}