0
\$\begingroup\$

Please Note by multiply I don't mean 11 * 11 = 11 But I mean 3*3=9 which is 1001 in binary

I am interested in knowing the following about multiplying numbers:

Let's say I have two 32-bit numbers like this:

A0 * 0B where A,B are 16 bits and 0 is 16 bit zero vector, then How can I perform multiply of these two numbers if I have only 16bit multiplier and 0/16/32 shifter?

For example let's say I have 10101010101010100000000000000000 * 00000000000000001111111101010111 How can I use 16bit multiplier here?


In case I have 0A * 0B then I use what I have to multiply A & B which gives 32 bit answer and I don't need to do anything about it.

In case I have A0 * B0 then I use what I have to multiply A & B which gives 32 bit answer that should appear at the most left so I use shift by 32 bit (the bits moved are filled with zeros)

\$\endgroup\$
11
  • 2
    \$\begingroup\$ Try doing it on paper with 4-bit values. I think that will show you what needs to be done. \$\endgroup\$ – Elliot Alderson Dec 26 '20 at 13:17
  • \$\begingroup\$ @ElliotAlderson already tried that which gave me the answer for the two examples I gave but things didn't work for this specefic case \$\endgroup\$ – MrCalc Dec 26 '20 at 13:29
  • \$\begingroup\$ @ElliotAlderson ok I took more examples and it seems the same as example 2 (Multiply A&B then add 16 zeros to the right) but still not sure about that, can you confirm? \$\endgroup\$ – MrCalc Dec 26 '20 at 13:35
  • 1
    \$\begingroup\$ Show us all of your work and ask a specific question. \$\endgroup\$ – Elliot Alderson Dec 26 '20 at 13:47
  • 1
    \$\begingroup\$ Your first task is to understand what you are trying to multiply. For example, A0 can be either 160 or -96. Which is it? In other words, binary algorithms for multiplication are different for signed and unsigned algorithms and if you don't define which, you have a very good chance of getting the wrong answer. \$\endgroup\$ – Brian Drummond Dec 26 '20 at 14:08
1
\$\begingroup\$

For 16 bit unsigned numbers A to D, where AB and CD are 32 bit numbers formed by concatenation,

AB * CD = (A*C << 32) + ((B*C + A*D) << 16) + B*D

\$\endgroup\$
5
  • \$\begingroup\$ Hi, Is the following equality true? (BC + AD)<<16 == (BC << 16) + (AD <<16)? \$\endgroup\$ – MrCalc Dec 26 '20 at 19:11
  • \$\begingroup\$ Assuming you correctly handle any potential overflows, yes. \$\endgroup\$ – Brian Drummond Dec 26 '20 at 23:02
  • \$\begingroup\$ Is there something similar when A,B,C,D are 8 bits? \$\endgroup\$ – MrCalc Dec 27 '20 at 9:24
  • \$\begingroup\$ Yes of course; and for decimal digits. You probably learned that one in primary school. \$\endgroup\$ – Brian Drummond Dec 27 '20 at 13:34
  • \$\begingroup\$ what if I have: a∙b=a_(N/2) a_(N/2-1)…a_1∙b_(N/2) b_(N/2-1)…b_1 How to write this as sigma? where each a and b is 16 bits so a in total is 16*N/2 bits \$\endgroup\$ – MrCalc Dec 27 '20 at 20:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.