2

my assignment is to write a compiler that will compile small programming language to a fake assembly language (register and memory cells are of undefined length).

What I have to do is converting such instruction:

a = b * c

to a set of INC, SHL i, ADD i instructions (where i is pointer to a memory, there's just one register available) that will perform multiplication. The problem is, that the algorithm must do it's work in O(log n) time.

Could anybody explain step-by-step the algorithm solving this problem? My friend has mentioned Booth-Mcsorley algorithm, but I hardly understand it.

EDIT: Fake assembly instructions include: READ, WRITE, LOAD i, STORE i, ADD i, SUB i, SHR i, SHL i, INC, RESET, JUMP k, JZERO k, JODD k (jump to k if register is odd)

TeoTN
  • 515
  • 1
  • 7
  • 22
  • Is some sort of if condtition (in asm form) allowed too, or only these three commands? Are numbers in binary 2-complement, or only positive, or...? – deviantfan Jan 05 '15 at 11:08
  • The old-time "advanced multiplication algorithms" are for hardware implementation, including Booth (take advantage of runs of identical bits) and McSorley (a radix-4 variant). Have a look at the standard binary algorithm, ask your friend what she was getting at, specify flow control and/or conditional arithmetic of your _fake_ assembly, let the world see how far your attempts got you. (I expect `undefined length` messing up two's complement.) – greybeard Jan 05 '15 at 11:13
  • What does the `n` in `O(log n)` represent? The magnitude of `a`, `b`, or `c`? Or the register bit length? The number of `1` bits in the binary representation of one of the numbers? Something else entirely? I think what you're asking about can be done in `O(n)` on the register bit length, or `O(log n)` on the magnitude of one of the numbers you're trying to multiply... – twalberg Jan 05 '15 at 15:42
  • @twalberg n of course represents magnitude of multiplicand and multiplier because register length is undefined. – TeoTN Jan 05 '15 at 17:30
  • @greybeard I've edited post and added all instructions. – TeoTN Jan 05 '15 at 17:34
  • (You might have included the interpretation of `n` in the post.) Looks an accumulator machine (`just one register available` leaving _available for temporary values without need to restore_ as an alternative interpretation). Is the register capable of holding values up to n²? If not, everything will be more tedious (all the more so without carry support). Given the lean choice of conditional instructions, only one of four basic binary multiplication variants would seem to suggest itself. – greybeard Jan 05 '15 at 20:40

1 Answers1

3

Since this is a fake assembler I wonder why is speed important? More likely it is to discourage you from implementing a naive iterative addition algorithm the length of which will be proportional to the magnitude of the right-hand operand (or the smaller of the two operands if you want a simple optimisation, but O(n) nonetheless).

The method of implementing multiply in instruction sets that lack a multiply instruction is to use shift-and-addition (essentially long multiplication in binary). Given the instructions you have been provided, this seems like the most likely required solution.

This question: How can I multiply and divide using only bit shifting and adding? may therefore be relevant. A shift+add implementation that is O(log2 n) in C is presented as an answer to What is the time complexity of this multiplication algorithm?, but could be adapted to your instruction set.

Community
  • 1
  • 1
Clifford
  • 88,407
  • 13
  • 85
  • 165