Computer Arithmetic Part-III

[Music] Welcome back. Let's take a look at faster multipliers, namely an order login square multiplier. So this is fairly simple to construct. So uh let's consider an n bit multiplier and an n bit multiplicand. So if we write the multiplier and the multiplicand multiplier here and the multiplicand here. So what we can do is we can construct n uh small

n partial sums where constructing each partial sum is very simple and also it can be done in parallel. So whenever we have a one we write uh the multiplican as is. If we have zero we just write zeros and every partial sum is offset by one position to the left as compared to

the partial sum before it. So if we are multiplying n bits we'll have n partial sums small n mind you. So all and all of these partial sums can be generated in parallel. So this partial sum can be generated simultaneously with this which can be generated simultaneously with this. So generating all the partial sums is very

easy. It takes a constant amount of time. So after that we need to add n numbers. All right. So for adding n numbers what we can do is we can have a tree of adders. So we can add the first and second here. We can add the third and fourth numbers here. The n minus 2 and n minus 3

numbers here. And uh so similarly we can have a tree of adders. So uh if we take a look at the sizes of the numbers, the first partial sum is n bits long and uh the last partial sum is uh 2 n minus one uh bits long. Right? So this is n over here and

n minus one over here. n minus one zeros. So at each level adding even 2n uh you know even numbers with 2n bits would take order of log to n time which is the same as order of login time because we ignore constants and even the base of the log is not important. So after that we have uh