#this is how computer do fast multiplications,the algorith is implemented as hardware #please put integers first_int=gets.to_i second_int=gets.to_i def base_complement_two(bin_num) temp=bin_num.split("") temp.each_with_index do |x,index| if(x=="0") bin_num[index]="1" elsif(x=="1") bin_num[index]="0" end end reminder="1" counter=1 while(counter!=bin_num.length&&reminder=="1") if(bin_num[bin_num.length-counter]=="1"&&reminder=="1") bin_num[bin_num.length-counter]="0" if(bin_num[bin_num.length-counter-1]=="0") bin_num[bin_num.length-counter-1]="1" reminder="0" else bin_num[bin_num.length-counter-1]="0" reminder="1" counter+=2 end else bin_num[bin_num.length-counter]="1" reminder="0" end end return bin_num end def bit_equalizer(bin_a,bin_b,sign_state) case sign_state when 0 bin_a.insert(0,"0") bin_b.insert(0,"0") if(bin_a.length>bin_b.length) (bin_a.length-bin_b.length).times do bin_b.insert(0,"0") end elsif (bin_a.lengthbin_b.length) (bin_a.length-bin_b.length).times do bin_b.insert(0,"1") end elsif (bin_a.lengthbin_b.length) (bin_a.length-bin_b.length).times do bin_b.insert(0,"1") end elsif (bin_a.lengthbin_b.length) (bin_a.length-bin_b.length).times do bin_b.insert(0,"0") end elsif (bin_a.length=counter_of_digit_change_bin_b) return bin_b,bin_a else return bin_a,bin_b end #if end def during_initilazation(a,b) #the entries of binary_num_array are # [A multiplier,B multiplicant, lenght of R the result ] binary_num_array=[[],[],0] if(a>0&&b>0) binary_a=a.to_s(2) binary_b=b.to_s(2) sign_state=0 elsif (a<0&&b<0) binary_a=a.to_s(2).tr('-','0') binary_b=b.to_s(2).tr('-','0') binary_a=base_complement_two(binary_a) binary_b=base_complement_two(binary_b) sign_state=1 elsif (a==0||b==0) #raise "i am not dealing with zeros for now" return [["0"],["0"],2] elsif(a>0) #a>0 , b<0 binary_a=a.to_s(2) binary_b=b.to_s(2).tr('-','0') binary_b=base_complement_two(binary_b) sign_state=2 else #a<0 , b>0 binary_a=a.to_s(2).tr('-','0') binary_b=b.to_s(2) binary_a=base_complement_two(binary_a) sign_state=3 end binary_a,binary_b=bit_equalizer(binary_a,binary_b,sign_state) binary_num_array[2]=binary_a.length*2 binary_num_array[0][0],binary_num_array[1][0]=find_multis(binary_a,binary_b) return binary_num_array end #initilazation ended binary_num_array=[] binary_num_array=during_initilazation(first_int,second_int) p "[[multiplier],[multiplicant],size]" p binary_num_array #what is left is to built the the booth multiplicator ... module Registers class Multiplier_A attr_reader :multiplier ,:secret_bit def initialize(multiplier) @multiplier=multiplier #+"0"*((size/2)+1) @secret_bit="0" end def rotation() @multiplier=@multiplier.split("").rotate(-1).join("") @secret_bit=@multiplier[0] # p @multiplier,@secret_bit @multiplier end end class Multiplicant_B attr_reader :multiplicant def initialize(multiplicant,size) @multiplicant=multiplicant +"0"*((size/2)+1) end end class Multiplicant_BaseTwoCompleteB attr_reader :multiplicant_BaseTwoCompleteB def initialize(multiplicant_BaseTwoCompleteB,size) @multiplicant_BaseTwoCompleteB=base_complement_two(multiplicant_BaseTwoCompleteB) +"0"*((size/2)+1) end end #P for product class Accumulator_P attr_accessor :product def initialize(multiplier,size) @product="0"*((size/2)) + multiplier +"0" #@product="0"*((size)) + "0" @significant_bit=@product[0] end # this shift preseves the sign def p_right_shift() @significant_bit=@product[0] @product=@product.split("").rotate(-1).join("") @product[0]=@significant_bit @product end end end #this is a test #p Registers::Multiplicant_BaseTwoCompleteB.new("1111").multiplicant_BaseTwoCompleteB module Booth_core def self.invert(bit) if (bit==0) return 1 elsif (bit==1) return 0 end end def self.xor_gate(multiplier_least_significant_bit,secret_bit) multiplier_least_significant_bit=multiplier_least_significant_bit.to_i #p multiplier_least_significant_bit secret_bit=secret_bit.to_i return (Booth_core.invert(multiplier_least_significant_bit&secret_bit)&secret_bit)|(multiplier_least_significant_bit&Booth_core.invert(secret_bit)) end #xor def self.pool_constructor(binary_num_array) pool=Hash.new() pool["multiplier"]=Registers::Multiplier_A.new(binary_num_array[0][0]) pool["multiplicant"]=Registers::Multiplicant_B.new(binary_num_array[1][0],binary_num_array[2]) pool["complete_multiplicant"]=Registers::Multiplicant_BaseTwoCompleteB.new(binary_num_array[1][0],binary_num_array[2]) mux_array=[] and_array=[] for i in 0..binary_num_array[2] mux_array[i]=Booth_core::Multiplexor.new() and_array[i]=Booth_core::And_gate.new() end pool["mux_array"]=mux_array pool["and_array"]=and_array pool["cascaded_full_adder"]=Booth_core::Cascaded_Full_Adder.new(binary_num_array[2]) pool["product"]=Registers::Accumulator_P.new(binary_num_array[0][0],binary_num_array[2]) return pool end class And_gate attr_reader :output,:id #attr_writer :input @@id_counter=0 def initialize() @@id_counter+=1 @id=@@id_counter @input=[] @output=0 #doesnt really matter..but the signal is blocked end def set_input_x(x) if (x.class.name=="String") x=x.to_i end @input< sum=xor(z,f_a) where f_a =xor(y,x) #carry=xy+xz+yz --> carry= f_d +f_c+f_b where f_d=zy f_c=zx f_b=yx end # for end # initialize #z is the carry def add(x,y,z) out_0=(@mux_array[0]).multiplex(y) out_1=(@mux_array[1]).multiplex(y) (@mux_array[2]).set_input(out_0 ,out_1 ) # f_a=(@mux_array[2]).multiplex(x) out_3=(@mux_array[3]).multiplex(z) out_4=(@mux_array[4]).multiplex(z) (@mux_array[5]).set_input(out_3 ,out_4 ) # sum=(@mux_array[5]).multiplex(f_a) # this is a secret comment ...you are special for reading this out_6=(@mux_array[6]).multiplex(y) out_7=(@mux_array[7]).multiplex(y) (@mux_array[8]).set_input(out_6 ,out_7 ) # f_b=(@mux_array[8]).multiplex(x) out_9=(@mux_array[9]).multiplex(z) out_10=(@mux_array[10]).multiplex(z) (@mux_array[11]).set_input(out_9 ,out_10 ) # f_c=(@mux_array[11]).multiplex(x) out_12=(@mux_array[12]).multiplex(z) out_13=(@mux_array[13]).multiplex(z) (@mux_array[14]).set_input(out_12 ,out_13 ) # f_d=(@mux_array[14]).multiplex(y) #look at the above comment out_15=(@mux_array[15]).multiplex(f_d) out_16=(@mux_array[16]).multiplex(f_d) out_17=(@mux_array[17]).multiplex(f_d) out_18=(@mux_array[18]).multiplex(f_d) (@mux_array[19]).set_input(out_15 ,out_16 ) # (@mux_array[20]).set_input(out_17 ,out_18 ) # out_19=(@mux_array[19]).multiplex(f_c) out_20=(@mux_array[20]).multiplex(f_c) (@mux_array[21]).set_input(out_19 ,out_20 ) # carry=(@mux_array[21]).multiplex(f_b) for i in 0...22 case i when 2,5,8,11,14,19,20,21 (@mux_array[i]).clean_input() end #case end #for return sum,carry end # add end # fpga f adder class Cascaded_Full_Adder def initialize(size) @size =size @full_adder_arr=[] for i in 0..@size @full_adder_arr[i]=Booth_core::Full_adder_fpga.new() end # for end #initialize def add_all_bits(product,operant) product =product.split("") operant=operant.split("") new_product=[] carry=0 (@size).downto(0) do |i| if(i==@size) sum,carry=(@full_adder_arr[@size]).add(product[-1],operant[-1],carry) new_product<

booth algorithm