I was wondering how many gates are needed to multiply a 2 bit number with a n bit number. One way is use 2 and gates and a full adder for each bit in the n bit number. That gives a complexity of 7n minus a constant.
I found a way to get 6n minus a constant. Is it known what is optimal?