Multiplication two 32-bit SIGNED numbers with Addition and Shifting

Question

I need to multiply two 32-bit SIGNED numbers using addition and shifting and get 64-bit number stored in memory locations $0408-$040F . This two numbers are stored in 8-bits memories.

 movb #$1F, $0400 ; the first number is $1F230001
 movb #$23, $0401
 movb #$00, $0402
 movb #$01, $0403
 movb #$F8, $0404 ; the second number is $F8012346
 movb #$01, $0405
 movb #$23, $0406
 movb #$46, $0407

I know how to multiply two 8-bits numbers with addition and shifting but I dont know how to go on with the others. I used an 16-bit Accumulator-D (accumulator-A 8bits MSB, accumulator-B 8bits LSB).

I am using CPU12: Reference Manual

Can you help me please, guide me or show me how to do it please? Thank you, I spent much time on this but I don't know how to do it with 32-bits numbers.

Answer 1

rewrite numbers as 8bit digits (base = 256) and solve multiplication algebraically:

 (a0+(a1<<8)+(a2<<16)+(a3<<24))
*(b0+(b1<<8)+(b2<<16)+(b3<<24))
------------------------------------
=(a0·b0                        )<< 0
+(a0·b1 + a1·b0                )<< 8
+(a0·b2 + a1·b1 + a2·b0        )<<16
+(a0·b3 + a1·b2 + a2·b1 + a3·b0)<<24
+(        a1·b3 + a2·b2 + a3·b1)<<32
+(                a2·b3 + a3·b2)<<40
+(                        a3·b3)<<48

Now there are just 8-bit * 8-bit multiply and 8/16 bit shift/add. Do not forget to carry on to higher digits (like add,adc,adc,...).

Hope I did not make a mistake

PS.

If you have 16 bit multiply can rewrite all process with base 65536 instead also can use Karatsuba algorithm for multiply for some speed up but be careful with the carry it needs more bits in such case.

Also I would do this on non signed numbers and add the sign evaluation later on

Here some related QAs of mine:

• Fast bignum square computation for karatsuba and other approaches
• Building a logarithm function in C without using float type for C++ 32 bit * 32 bit multiply
• Cant make value propagate through carry for 32 bit ALU operations in C++