Is it possible to do multiplications only with operators &, |, + and -?

Asked

Viewed 2,453 times

4

I have to create a program with the Assembly language K & S Model 2 that multiplies one number by another, the problem is that this language does not provide a multiplication operation. So I thought of doing multiplications with additions, for example:

3 x 5 = 5 + 5 + 5 (3 vezes o 5) = 15

This language also does not provide a direct way to make a cycle (or loop), nor a record comparison statement, for example to see if they are equal, ie if it has the same number.

This Assembly language provides only operators of bitwise which I’m not very familiar with. I know that doing AND bit by bit is like doing a multiplication of numbers but converted into binaries, for example:

3 & 2

First we have to convert to binary:

  11 (3)
& 10 (2)
==== 
  10 (2)

I honestly don’t see how I can do a multiplication using this operation, if only I could make a loop anyway...

assembly bitwise
  • 1

    What types of conditional deviation does this language have? Is it possible for example to say, "deviate if such a record is zero"? Most likely the solution to your problem will be there, not the operators bitwise.

  • Yes! As I said in the answer, I don’t know exactly how these commands work. I assume that "ALU RESULT" refers to the "result of the last arithmetic and logic operation performed", and wrote the pseudo-code based on this premise. It would even be possible to adapt the algorithm to a language without conditional deviation, provided that the unconditional deviation allowed to use a memory or register value as the point of arrival, but I see that in your case this is not how the BRANCH works (it asks for an address hardcoded). So the output is to use BNEG or BZERO same (in my code, BNEG)

  • 2

    You can use the 4th series multiplication algorithm to make the account more efficiently than just making a lot of sums.

  • https://pt.wikipedia.org/wiki/Multiplica%C3%A7%C3%A3o_por_duplica%C3%A7%C3%A3o

  • @hugomg Cool this algorithm, but I don’t remember seeing you at school no. Although my 4th grade is a lot further away than yours... : P

  • 1

    This algorithm is the base 2 version of the school’s algorithm (which uses base 10)

  • 1

    Aaaaah, now everything makes sense! : I actually thought [subconsciously] about suggesting a variation of it at first, but how this architecture does not support shift left it was going to be a little bit more complicated... I preferred to keep the answer really, after all "first make it work, then make it fast" :P

Show 2 more comments

2 answers

5

You can do a multiplication [integer] using only the sum (+), provided that you have access to a conditional deviation operator that deviates if such registration is zero. By your link, there are two such operators: BZERO (deviates if the ALU result is zero) and BNEG (deviates if the ALU result is less than zero).

I did not understand very well how this architecture works (nor do I intend to delve into it), so I will respond with pseudo-code:

  1. Guard -1 on record A;
  2. Store the multiplier in the record B;
  3. Save the multiplying in the record C;
  4. Guard 0 on record D;
  5. Add the records A with B and save the result in B; (i.e. decreases the multiplier)
  6. If the result is less than zero, go to 9;
  7. Add the records C and D and save the result in D;
  8. Go back to 5;
  9. End of the program. (D contains the result of multiplication)

That is, each time you decrement the multiplier, you add it by multiplying it to the result. You are then calculating n x m adding up m n times.

Note: this algorithm works even when m is negative, but not when n is negative - it will enter an infinite loop. The solution in this case would be to have two algorithms: one that decreases to zero, and one that increases to zero, and choose between one and the other depending on whether n is positive or negative.

1

I did it this way and it worked:

1)LOAD R1 22
2)LOAD R2 23
3)LOAD R3 24
4)ADD R0 R0 R3
5)STORE 21 R0
6)ADD R2 R2 R1
7)STORE 23 R2
8)BZERO 9
9)BRANCH 4
10) HALT

Browser other questions tagged assembly bitwise

You are not signed in. Login or sign up in order to post.