signed 32bit booth's multiplication (fastest in average)

denis_potatoe

This multiplication is not the fastest I have made. Some are quicker but not for every operation. This is probably the best in average you could do for 32bit signed multiplication. This one loop only 16 times at maximum (if you don't make overflow). I hope you will enjoy this: entry 'init result value mov R,#0 'make x the smallest 'optimization to ensure maximal 16 loops if no overflow abs x1,x abs y1,y CMP x1,y1 wc,wz if_nc mov y1,y if_nc mov y,x if_nc mov x,y1 test x,#1 wz if_nz sub R,y shl y,#1 loop test x,#1 wc test x,#2 wz if_nz_and_nc sub R,y 'if 10 sub if_z_and_c add R,y 'if 01 add shl y,#1 wz if_nz sar x,#1 wz if_nz cmp x,TRUE wz if_nz jmp #loop ret x LONG -99999 'ARG1 y LONG -2 'ARG2 R LONG 0 'RESULT x1 LONG 0 y1 LONG 0 TRUE LONG -1 here is a shorter one but not very optimised (negative number do 32 loops) : DAT org entry mov R,#0 test x,#1 wz if_nz sub R,y shl y,#1 loop test x,#1 wc test x,#2 wz if_nz_and_nc sub R,y if_z_and_c add R,y shl y,#1 wz if_nz shr x,#1 wz if_nz jmp #loop ret x LONG 12 'ARG1 y LONG 12 'ARG2 R LONG 0 'RESULT For information I have no propeller, I made this for a friend with a simulator. Here is the C version : #include int main(int argc, char** argv) { int multiplicand = atoi(argv[1]); int multiplier = atoi(argv[2]); unsigned int A=multiplicand; unsigned int P=0; int Q=multiplier; if (multiplicand < multiplier) { // swap P,Q could be made with xor unsigned int temp = Q; Q = A; A = temp; } if (Q&1) P-=A; A=1; A

denis_potatoe

optimised only 16 loops max (if no overflow):

DAT
org
entry
'init result value
mov R,#0

'make x the smallest
'optimization to ensure maximal 16 loops if no overflow
abs x1,x
abs y1,y
CMP x1,y1 wc,wz
if_nc mov y1,y
if_nc mov y,x
if_nc mov x,y1

test x,#1 wz
if_nz sub R,y
shl y,#1
loop test x,#1 wc
test x,#2 wz
if_nz_and_nc sub R,y 'if 10 sub
if_z_and_c add R,y 'if 01 add
shl y,#1 wz
if_nz sar x,#1 wz
if_nz cmp x,TRUE wz
if_nz jmp #loop
ret
x LONG -99999 'ARG1
y LONG -2 'ARG2
R LONG 0 'RESULT
x1 LONG 0
y1 LONG 0
TRUE LONG -1


not optimised but short :

DAT
org
entry
mov R,#0
test x,#1 wz
if_nz sub R,y
shl y,#1
loop test x,#1 wc
test x,#2 wz
if_nz_and_nc sub R,y
if_z_and_c add R,y
shl y,#1 wz
if_nz shr x,#1 wz
if_nz jmp #loop
ret
x LONG 12 'ARG1
y LONG 12 'ARG2
R LONG 0 'RESULT

C version :

#include <stdio.h>

int main(int argc, char** argv)
{
int multiplicand = atoi(argv[1]);
int multiplier = atoi(argv[2]);

unsigned int A=multiplicand;
unsigned int P=0;
int Q=multiplier;
if (multiplicand < multiplier)
{ // swap P,Q could be made with xor
unsigned int temp = Q;
Q = A;
A = temp;
}
if (Q&1)
P-=A;
A<<=1;
while (Q!=-1 && Q) {
switch(Q&3) {
case(2):
P-=A;
break;
case(1):
P+=A;
break;
}
Q>>=1;
A<<=1;
}

printf("%i\n", multiplicand*multiplier);
printf("%i\n", (int)P);

}

If you could implement it better in pasm, please let me now.

Regards,

denis

denis_potatoe

You probably noticed, something was missing in C version :

int main(int argc, char** argv)
{
int multiplicand = atoi(argv[1]);
int multiplier = atoi(argv[2]);

unsigned int A=multiplicand;
unsigned int P=0;
int Q=multiplier;
if (abs(multiplicand) < abs(multiplier))
{ // swap P,Q could be made with xor
unsigned int temp = Q;
Q = A;
A = temp;
}
if (Q&1)
P-=A;
A<<=1;
while (Q!=-1 && Q) {
switch(Q&3) {
case(2):
P-=A;
break;
case(1):
P+=A;
break;
}
Q>>=1;
A<<=1;
}

printf("%i\n", multiplicand*multiplier);
printf("%i\n", (int)P);

}

Peter Jakacki

Hi Denis, could you highlight your code and use the CODE attributes # found in the "Go Advanced" edit mode? Otherwise the forum software mangles all the whitespace etc. Cheers.

Perry

This is a great piece of code, it boosted my color video render to about 438 lines per second. At 112 lines per frame that is almost four frames per second.

I am pleased!
Perry

JonnyMac

I added Denis's code to my PASM work template and did a test; not for time, just to ensure that it works (is compared against Spin). It ran for 30 minutes without error so I'm sure my formatting didn't foul anything.