This is a simple exercise to use some Matlab expression manipulation functions. Our goal is to espress the product of two 64 Bit numbers as function of their 8 Bit sub groups. More precisely, we are going to use the following formula for 2n Bit data:

D = Dh*2^n + Dl

whereby D is a 2n Bit number, Dh are the upper n bits and Dl the lower n bits.

We multiply two Bit numbers, A and B, and we want to display the final analytical formula with matlab. The following code is very spartan, but it does the job:

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 |
syms A B % 64 Bit syms Ah Al Bh Bl % 32 Bit syms Ahh Ahl Alh All Bhh Bhl Blh Bll % 16 Bit syms Ahhh Ahhl Ahlh Ahll Alhh Alhl Allh Alll % 8 Bit syms Bhhh Bhhl Bhlh Bhll Blhh Blhl Bllh Blll % 8 Bit % The formula is applied to each sub group of bits A = Ah*2^32 + Al; B = Bh*2^32 + Bl; Ah = Ahh*2^16 + Ahl; Bh = Bhh*2^16 + Bhl; Al = Alh*2^16 + All; Bl = Blh*2^16 + Bll; Ahh = Ahhh*2^8 + Ahhl; Ahl = Ahlh*2^8 + Ahll; Alh = Alhh*2^8 + Alhl; All = Allh*2^8 + Alll; Bhh = Bhhh*2^8 + Bhhl; Bhl = Bhlh*2^8 + Bhll; Blh = Blhh*2^8 + Blhl; Bll = Bllh*2^8 + Blll; % - A and B are multiplied -> A*B; % - the equations are put into each other till the product is function of % bottom variables (Bhhh, Bhhl, ...) -> sub(sub()); % - the product is expanded as sum of monomials -> expand(); expr = expand(subs(subs(A*B))); % Coefficients of expr are gathered in a vector in decreasing order C = fliplr(coeffs(expr)); C_str = string(C); % Coefficients are collected inside the expr as common factors outside % the brackets expr = collect(expr, C); expr_str = string(expr); C2 = log2(C); % Coefficients are replaced with exponents of powers of two C2_str = strcat("2^",string(C2)); %Prefix 2^ is added before exponents % Coefficients are replaced with their corresponding power of two result = replace(expr_str,C_str,C2_str) |

The result is

(Ahhh*Bhhh)*2^112 + 2^104*(Ahhh*Bhhl + Ahhl*Bhhh) + 2^96*(Ahhl*Bhhl + Ahhh*Bhlh + Ahlh*Bhhh) + 2^88*(Ahhh*Bhll + Ahhl*Bhlh + Ahlh*Bhhl + Ahll*Bhhh) + 2^80*(Ahhl*Bhll + Ahll*Bhhl + Ahlh*Bhlh + Ahhh*Blhh + Alhh*Bhhh) + 2^72*(Ahlh*Bhll + Ahll*Bhlh + Ahhh*Blhl + Ahhl*Blhh + Alhh*Bhhl + Alhl*Bhhh) + 2^64*(Ahll*Bhll + Ahhl*Blhl + Alhl*Bhhl + Ahhh*Bllh + Ahlh*Blhh + Alhh*Bhlh + Allh*Bhhh) + 2^56*(Ahhh*Blll + Ahhl*Bllh + Ahlh*Blhl + Ahll*Blhh + Alhh*Bhll + Alhl*Bhlh + Allh*Bhhl + Alll*Bhhh) + 2^48*(Ahhl*Blll + Ahll*Blhl + Alhl*Bhll + Alll*Bhhl + Ahlh*Bllh + Allh*Bhlh + Alhh*Blhh) + 2^40*(Ahlh*Blll + Ahll*Bllh + Allh*Bhll + Alll*Bhlh + Alhh*Blhl + Alhl*Blhh) + 2^32*(Ahll*Blll + Alll*Bhll + Alhl*Blhl + Alhh*Bllh + Allh*Blhh) + 2^24*(Alhh*Blll + Alhl*Bllh + Allh*Blhl + Alll*Blhh) + 2^16*(Alhl*Blll + Alll*Blhl + Allh*Bllh) + 2^8*(Allh*Blll + Alll*Bllh) + Alll*Blll

## Leave a Reply