How Many More Times?

multiplying without multiplying on RISC-V

“Draw a picture of a giraffe multiplying things.” I have no words.

There’s often short sequences of shift, add, and subtract instructions that you can use to multiply an integer by a constant. For instance, instead of using a general-purpose multiply subroutine on a RV32I (which lacks a multiply instruction) to multiply by 10 in an ASCII decimal-to-binary routine, you can do this:

# Read an ASCII unsigned decimal string into a register. The parsing of
# the value stops when we read the first non-decimal character.
#
# input registers: 
# a0 = pointer to number to convert from decimal, 
# terminated with non-decimal char.
# output registers: 
# a0 = pointer (advanced to point to non-decimal char)
# a1 = number
# a2 = error check: 0 if no digits found, otherwise 1

from_decu:
	li	a1, 0
	li	a2, 0
	li	a7, 9

from_decu_digit:
	lb	a6,(a0)
	addi	a5, a6, -'0'
	bgtu	a5, a7, from_decu_done

	li	a2, 1
	slli	a3, a1, 1	# a3 = a1 * 2
	slli	a4, a1, 3	# a4 = a1 * 8
	add	a1, a3, a4	# a1 = a1 * 10
	add	a1, a1, a5	# add in new digit
	addi	a0, a0, 1
	j	from_decu_digit

from_decu_done:
	ret

The three bolded instructions multiply the a1 register by 10, expressed as a multiply-by-two plus a multiply-by-eight. As 2 and 8 are both powers of two, we can do left shifts to form the multiples.

That one is relatively obvious. But not all of them are so simple. Consider multiplying by 95, one can achieve this with the following instructions:

	# a0 = a0 * 95
	slli	a1, a0, 6
	slli	a2, a0, 5
	add	a1, a1, a2
	sub	a0, a1, a0

I enjoy finding the shortest list of instructions to accomplish a given task, so I have come up with a list of RISC-V assembly instructions (and equivalent python expressions) to multiply numbers by constants from 0 to 256 without using a multiply instruction. I’m sure there are some tricks I don’t know, I’d enjoy getting feedback with any corrections or improvements to this table. I only used add, subtract, and left shift; it’s possible that right shift or some other instructions might open up some new possibilities.

Notes on Python Fragments with Intermediate Variables: For clarity and to accurately reflect the operation count when a sub-expression is reused (Common Sub-expression Elimination - CSE), some fragments are written using a lambda structure (lambda n_in: (lambda y: Y_EXPR)(X_EXPR))(n). This is a way to represent y = X_EXPR; result = Y_EXPR_using_y as a single evaluable expression while making the CSE explicit.

c=45, 75, 81, 85, 90, 91, 93, etc.: These use the lambda form to show reuse of an intermediate calculation (y) to achieve the stated minimal operations. For example, for c=45, y=(n<<2)+n (2 ops), then (y<<3)+y (2 ops on y), totaling 4 operations.

The operation counts (e.g., "2S, 1A" means 2 shifts, 1 addition) list the fundamental operations on n or derivatives of n to achieve the final product.

I found these equations by looking for:

• “Simple forms” such as:

\((2^k, 2^k \pm 1) \)

• Common 3-Operation patterns, such as 2 shifts, one arithmetic operation; one shift, two arithmetic operations; and two shifts and one arithmetic operation, chained.

\((K = 2^{k_1} \pm 2^{k_2}), (K = 2^{k_1} \pm 2), (K = (2^{k_1} \pm 1) \cdot 2^{k_2}) \)

• CSD (Canonical Signed Digit) Method: https://en.wikipedia.org/wiki/Non-adjacent_form

• Alternative Sum/Difference of Powers: https://artofproblemsolving.com/wiki/index.php?title=Sum_and_difference_of_powers

• Factorization

• Breadth-first search: https://en.wikipedia.org/wiki/Breadth-first_search

• When a number has 3-adjacent 1-bits in it, Hacker’s Delight suggests looking for a pattern with a subtraction in it.

Perhaps next time you need to multiply something by 235, you’ll find this handy.