Multiplication... Without multiplication

[ResidentBiscuit]

Ok so I've been given a handful of assembly assignments, and one of them is just to read in 2 integers, multiply them together, and then display the result. I was wondering what you think about my algorithm for multiplying using addition.

int k = 0; int ans = 0;
if(x - y < 0)	//x < y
{
   do
   {
	ans = ans + y;
	k = k + 1;
    }while(k <= x)  //Not sure how to translate this condition into assembly
}
else
{
    do
    {
	ans = ans + x;
	k = k + 1;
    }while(k <= y)
}

It's supposed to be as efficient as possible. I went with the if(x - y < 0) route cause I figured if I found the smallest of the two variables, I could loop through that many times adding the other variable to itself that many times. I figured this would lead to a better average-case scenario, and worst case scenario would of course be the same. The only thing I could see to improve upon would be the use of k. But I don't think there's a way to get rid of that extra variable

[Duthomhas]

Your algorithm is really over-worked.

Remember, that each bit in the multiplier represents a binary power. So the result of multiplying is the result of adding powers of the multiplicand.

For example, if we multiply 5 and 10:

    0101 <-- bits in multiplier
--------
    1010 <-- bits in multiplicand, right-aligned with the first set bit in the multiplier
+ 1010   <-- same, right-aligned with the next set bit in the multiplier
--------
  110010 <-- sum

The algorithm to do this is very simple. (For simplicity, I'll refer to the integers being multiplied as a and b.)

result = 0
Loop while a is not zero:
  if a's least-significant bit is set:
    result += b
  a >>= 1
  b <<= 1

This works, of course, only with an unsigned value for a. If you wish to work with signed integers, you will have to do a little extra work to make sure that a is unsigned for the algorithm. If you think carefully, that should only take an extra test and a couple of sign-inversions before entering the loop.

That leaves a very short, clean assembly routine, where the only conditions you must test are a less-than-zero for the extra test for signed numbers, and a test for zero for the loop.

Good luck!

[ne555]

I found simpler to descend decfsz iter,f ; decrement file, skip if zero. Save in file
But you already know how to compare numbers, ¿what is your issue?

As to improve the algorithm http://mathworld.wolfram.com/RussianMultiplication.html

[Duthomhas]

@ne555
Are you OK? (Your last post doesn't make a whole lot of sense.)
Also, the "Russian Multiplication" algorithm is the exact one I suggested above.

[ResidentBiscuit]

Well, we aren't using x86 or anything "real". We use this ridiculous simulator that only has like 12 opcodes, and none of which are bitwise anything. So I'm not sure I could use your suggestion Duoas :( The only operations we have are add, subtract, and a skip condition.

[ne555]

Let's try again

for(int K=0; K<n; ++K)
  /* do something that does not use K. */

As all you care is that the snip gets executed n times, you could also do for(int K=n; K!=0; --K) that translates to

movlw  qty; 
movwf  K
loop:
  ;whatever
  decfsz  K,1 ;1 saves the result in f, 0 in w
  bra  loop

(assembly PIC)

The second paragraph refers to

if(x - y < 0)	//x < y
while(k <= x)  //Not sure how to translate this condition into assembly 

As use subtraction, check sign flag was already used, I can't understand the difficulty to pass from x<y to x<=y


@ResidentBiscuit: ¿not even rotate? Still a rlf can be implemented as x+x. As for rrf, just keep going to the left...
I expect that you do have pointers.

@Duoas
I did not see your post at that time, the connection is really bad lately.
Thanks for your concern, everything is fine (I guess)

[naraku9333]

This seems to work, though not very efficient as I didn't want to add the extra conditions to test which is smaller.

Org 100
Clear
loop, Load w
Add x
Store w
Load y
Subt z
Store y
Load y
Skipcond 400
Jump loop
Load w
Output
Halt
w, Dec 0
x, Dec 10
y, Dec 5
z, Dec 1

[Duthomhas]

Ah, I get it now.
Glad you are (probably) okay.
:O)

[ResidentBiscuit]

@naraku, that's actually like the exact thing I did. How did you know what program we're using??

[naraku9333]

Googled the file extension you posted in the other thread. Found the simulator and documentation, the opcodes where the same so I put 2 and 2 together. My google skills are pretty good, its rare I can't find what I'm looking for.

[ResidentBiscuit]

Ah very nice. I'm impressed. Professor seemed impressed that I went ahead and checked to see which number is smaller, I didn't think it was a big deal. I guess hardly anyone else did that though

[Duthomhas]

It makes a difference with algorithm speed, so yours performs faster than everyone else's on all inputs.