A Problem

TOY86 does not support multiplication natively. In general, (unsigned) multiplication can be done by Horner's method. But if we restrict the multiplier to be a constant, it can be done more efficiently using the lea instruction. (Unfortunately, the result of an lea instruction has only 12 bits, so this may not be useful in practice.) For example, multiplying register RA by 11 requires only two instructions:

lea RB, RA + RA * 4
lea RA, RA + RB * 2

A question naturally arises: given a constant multiplier, what is the least number of lea instructions required to do the multiplication? Or more interestingly, what is the least number of bytes required to do the multiplication? For example, if we use "lea RA, RA + RA" to multiply RA by 2, it takes 4 bytes to finish the job; but obviously 3 bytes are sufficient, by using either "add RA, RA, RA" or "shl RA, RA, 1". And what about the least number of registers?

--
Looking at the lea instruction on x86 or the instructions 2ADDU, 4ADDU, 8ADDU, and 16ADDU on Knuth's MMIX machine poses the same problem.