While multiplication is defined in the context of repeated addition, implementing it that way algorithmically is not nearly as efficient as some other approaches. One algorithm for multiplication that is an order of magnitude faster is to halve one number while doubling the other. I gave myself the challenge of implementing this algorithm in AARCH64 Assembly, and it was not too hard.
This exercise allowed me to work through a few operations.
- In order to double a number, you shift its bits left.
- In order to cut it in half, you shift it right.
- In order to check if a number is negative, you perform a logical and with the most significant bit.
- In order to reverse the sign of a number, you perform an exclusive or (eor) on the bits.
- In order to check if a number is odd or even, you perform a logical and with the least significant bit
Here’s the code. I used the debug.s file as presented by Stephen Smith in “Programming with 64-bit ARM Assembly Language.” The main section of the code is a series of unit tests that show the algorithm works for various ases of positive, negative, and zero value operands.
.include "debug.s" .global main main: mov x1, #55 //First multiplicand mov x2, #12 //Second multiplicand bl adder mov x1, #-55 //First multiplicand mov x2, #12 //Second multiplicand bl adder mov x1, #-5 //First multiplicand mov x2, #-32 //Second multiplicand bl adder mov x1, #5 //First multiplicand mov x2, #-3 //Second multiplicand bl adder mov x1, #0 //First multiplicand mov x2, #-3 //Second multiplicand bl adder mov x1, #10 //First multiplicand mov x2, #0 //Second multiplicand bl adder endProgram adder: printStr "----" printReg 1 printReg 2 cmp x1, #0 //If either value is 0, we are done b.eq done cmp x2, #0 b.ne prep mov x1, x2 b done prep: mov x3, #0 //keeps track of signedness. mov x4, #0 //running addend //ensure A is positive cmp x1, 0 B.GE step2 mov x3, 1 eor x1,x1, #0xfffffffffffffffe eor x1,x1, #0x1 add x1, x1, 1 //Ensure B is postive step2: cmp x2, 0 B.GE step3 eor x3, x3, 1 eor x2,x2, #0xfffffffffffffffe eor x2,x2, #0x1 add x2, x2, 1 step3: cmp x2, #1 b.eq wrapup and x9, x2,#0x1 CMP x9, #0x1 B.LT step4 add x4, x4, x1 step4: LSL x1, x1, 1 LSR x2, x2, 1 b step3 wrapup: add x1, x1, x4 cmp x3, #1 b.ne done //convert to negative eor x1, x1, #0xfffffffffffffffe eor x1, x1, #0x1 add x1, x1, 1 done: mov x0, x1 //final answer printReg 0 ret
One stumble I made was in the xor to convert from positive to negative and the reverse. The compiler seems to treat a set of a 1s as an overflow condition, so I treated the least significant bit separately. This must be a common operation, and I am sure there is a better way to do it.
37 Instructions for the adder function, if we strip out the print statements. Thus, this is obviously going to beat the iterative approach for any number where the smaller operand is 37 or larger. Assuming I solve the eor problem above, that removes 3 more operations. Plus, an iterative approach is going to have a minimal amount of control operations, lets guess 5 (two comparisons and the final ret). That means 29 operations.
More interesting is the growth of the complexity of the algorithm presented here. As B gets larger with the naive algorithm, the number of operations increases linearly. O(B). For this algorthm, the number of operations increases based on the log base2 of B. Thus, for very large values of B, the halving/doubling approach would take much less time.