While looking at the ARM instruction set, you notice that the
ADD instruction has the so-called "Flexible second operand", which can be abused for quick multiplication. For example, the following instruction multiplies register
r1 by 17 (shifting it left by 4 bits and adding to itself):
ADD r1, r1, r1, LSL #4 ; LSL means "logical shift left"
The subtraction instruction has that feature too. So multiplication by 15 is also easy to implement:
RSB r1, r1, r1, LSL #4 ; RSB means "reverse subtract", i.e. subtract r1 from (r1 << 4)
So this is an excellent optimization opportunity! Certainly, when you write in a C program
x *= 15, the compiler will translate that to some inefficient code, while you could replace it by
x = (x << 4) - x, and then the compiler will generate better code!
Quickly, you come up with the following cunning plan:
Write a program or a subroutine, in any language, that receives one parameter
m, and outputs a C optimizing macro, like the following (for
m = 15):
#define XYZZY15(x) (((x) << 4) - (x))
or (which is the same)
#define XYZZY15(x) (-(x) + ((x) << 4))
- The macro's name is essential: magic requires it.
- Parentheses around
xand the whole expression are required: ancient C arcana cannot be taken lightly.
- You can assume
mis between 2 and 65535.
- The input and output can be passed through function parameters,
stdin/stdoutor in any other customary way.
- In C, addition and subtraction have tighter precedence than bit shift
<<; use parentheses to clarify order of calculations. More parentheses than necessary is OK.
- It is absolutely vital that the C expression be optimal, so e.g.
x+x+xis not acceptable, because
x + xand
x << 1are equivalent, because both require one ARM instruction to calculate. Also,
(x << 1) + (x << 2)(multiplication by 6) requires two instructions, and cannot be improved.
- You are amazed to discover that the compiler detects that
(x << 0)is the same as
x + (x << 0)is an acceptable expression. However, there is no chance the compiler does any other optimizations on your expression.
Even though multiplication by 17 can be implemented in one instruction, multiplication by 17*17 cannot be implemented in two instructions, because there is no C expression to reflect that:
#define XYZZY289(x) x + (x << 4) + (x + (x << 4) << 4) // 3 operations; optimal
In other words, the compiler doesn't do common sub-expression elimination. Maybe you will fix that bug in version 2...
This is code-golf: the shortest code wins (but it must be correct, i.e. produce correct and optimal expressions for all
Please also give example outputs for
m = 2, 10, 100, 14043 and 65535 (there is no requirement on the length of the expression - it can contain extra parentheses, whitespace and shift left by 0 bits, if that makes your code simpler).