8 bit binary multiplication using add/shift

[mikeOJ]

Hi All,

i've read a lot about of theory about implementing multiplications using add and shift but i still cant seem to crack it when i'm putting it into code. from my understanding:

we have 2 variables, a multiplier and a multiplicand

we want to test the LSB of the multiplicand, if its 0 we dont add, simply shift the multiplicand in the results vector
IF its a one we add the multiplier to what ever result we currently have, check that there has been no carry in the status register and wrap around the loop until the multiplicand reg is all zeros.

i've spent all day reading pseudo code but still cant seem to crack it. i know i'm not storing the result correctly and something to do with my use of the partial products is off too..

could someone give me the rundown.

 

[Ian Rogers]

You better look through this thread.. https://www.electro-tech-online.com/threads/adc-result-in-three-decimal-point.132548/

Then tell me if you "get it" or am I bad at explanations.....

 

[mikeOJ]

Nono, far be it from me to undermine a man of your intellectual stature. That link seems more than enough, i'm about to go through it with a fine tooth comb and will let you know if anything pops up.

Incidentally, i know from decimal multiplication the reason we shift the multiplicand to the right but i cant see the logic for shifting the multiplier to the left. Its just something id like to get to grips with since my next venture will be binary division.

Thanks

 

[mikeOJ]

Mr rogers..

Based on your post below:

lets take 4 x 5 = 20:-

Multiplicand = 0100 (4)
Multiplier = 0101 (5)

Register = 00000 (0)

First we check the lsb of the multiplier (5)
We see that it is a 1. ( An add condition ).. So we put the multiplicand (4) into a register

Register = 4..

Secondly, we shift the multiplier right >> one position WHILE we shift the multiplicand left << one position.

Multiplicand = 01000 (8)
Multiplier = 0010 (2)

Register still =4

We now test the lsb again and see a 0. (A no add condition)
But we still shift..

Multiplicand 010000 (16)
Multiplier 0001 (1)

Now we test again.. The lbs is 1 (An add condition ). Add the now 16 to the original 4. so:- Register = 20

Shift for the last time..

Multiplicand = 010000 (32)
Multiplier = 0000 (0)

Register = 010100 (20)

i have written some code which i have posted below.

		MOVLW	b'0101'
		MOVWF	multiplier


		MOVLW	b'0100'
		MOVWF	multiplicand

		MOVFF	multiplicand, cycle_count	
		DECFSZ	multiplicand2


					
HERE		BTFSC	multiplier,0
		ADDWF	register,1
		RRCF	multiplier,1
		BCF		0XFD8,0
		RLCF	multiplicand,1
		BCF		0XFD8,0
		MOVWF	multiplicand,1
		DECFSZ	cycle_count

		GOTO	HERE

However for some reason the MOVLW toward the end of the cycle for multiplicand, never returns to the 1 reg all i get is b'1'. Is there any reason for that. Additionally am i doing the right thing by counting the cycles and using that to determine when the right amount of additions have been completed and also how would something like this translate to 16 bit addition with carry bits ext..

 

[kubeek]

I think both multiplier and multiplicand need to be shifting to right, i.e.you first add the mutliplier, then shift multiplicand into result, so lsb of mutliplicand gets stored in msb of result. This leaves you with the high byte in mutliplier and low byte in result.

 

[dougy83]

Hope this is pseudo-code-like enough for you:

uint16 multiply(uint8 a, uint8 b)
{
	uint16 result = 0;
        uint8 bits = 8;
	while(bits > 0)
	{
		result = result * 2;
		
		if(a & 0x80)
			result = result + b;
			
		a = a * 2;
                bits--;
	}
	
	return result;
}

 

[Ian Rogers]

I think both multiplier and multiplicand need to be shifting to right, i.e.you first add the multiplier, then shift multiplicand into result, so lsb of multiplicand gets stored in msb of result. This leaves you with the high byte in multiplier and low byte in result.

No he's adding the multiplier to the result not the multiplicand.. You shift the multiplier right and the multiplicand left.

Mike!! the assembly code is there as well.....

 

[mikeOJ]

yep, its definitely working shifting the multiplicand/multiplier the way Ian suggested.

using the instruction

RLCF multiplicand,1 ; SHOULD shift the multiplicand right and leave the result in the WREG so that when the loop returns to

ADDWF register,1 ; The literal (4) already in the intermediate result register from the first addition is added to the number in the WREG (which after shifts is 16)

however the RCLF multiplicand,1 instruction just isnt shifting.



Ian i did see the code and am reading through it but for me, trying to decipher the 16 Bit without first having a grasp on the 8bit is like.. searching for a resistor in the desert

 

[mikeOJ]

just seen this error in the first code i pasted, which is the reason for the WREG 'not responding how i intended'

		MOVWF	multiplicand,1

should be

MOVFF multiplicand, WREG

meaning that the new shifted number is moved to WREG so that it can be added to the previous result

so thats fine but some explanation of the 16 Bit operation would be greatly appreciated. The carry operation and checking of LSB/MSB perplexes me

 

[Ian Rogers]

yep, its definitely working shifting the multiplicand/multiplier the way Ian suggested.

using the instruction

RLCF multiplicand,1 ; SHOULD shift the multiplicand right and leave the result in the WREG so that when the loop returns to

ADDWF register,1 ; The literal (4) already in the intermediate result register from the first addition is added to the number in the WREG (which after shifts is 16)

however the RCLF multiplicand,1 instruction just isnt shifting.



Ian i did see the code and am reading through it but for me, trying to decipher the 16 Bit without first having a grasp on the 8bit is like.. searching for a resistor in the desert

I must admit... The 32bit multiply was different than my comments ( This is confusing everyone). It DOES shift right with both multiplier AND multiplicand but when its written out it works out the same..

Here is the other way..

Take 12 * 6

1100 = 12
0110 = 6

ONLY shift the top part (multiplicand)

shift

0000.0110 Carry = 0

shift

0000.0011 Carry = 0

shift

0000.0001 Carry = 1
add in mutiplier
0110.0001

shift

0011.0000 Carry = 1
add in multiplier
1001.0000

last shift

0100.1000

I'm sure there are MANY other ways...

 

[mikeOJ]

The first one is going ok but ill give that way a go now too. I want to be in no doubt in my understanding

what method is used to determine how many times to go through the loop, what do we use to let the micro know how many bits we need to shift and consequently when we have reached the right number of shifts for a valid result

 

[Ian Rogers]

4x4 multiplication = 4 loops

8x8 Multiplication = 8 loops.

16x16 Bet you can guess...

Some people start with a flag in the result register and wait until it carries...

Look at this web site for the different ways .