# Optimizing integer multiplication

I was quite obsessed with the idea of optimizing integer multiplication by using bit shifts so that I noticed a beautiful pattern in the binary representation when I looked at some results of previous equations, I wrote. I wrote a small brute-force algorithm to get all possible numbers which can be optimized a bit as constant factor of a multiplication. The algorithm is implemented in JavaScript, so if you're interested in the source code, feel free to read it.

 0 * n 1 * n 000000000000 n - n 000000000001 n 000000000010 (n << 1) 000000000011 (n << 1) + n 000000000100 (n << 2) 000000000101 (n << 2) + n 000000000110 (n << 2) + (n << 1) 000000000111 (n << 3) - n 000000001000 (n << 3) 000000001001 (n << 3) + n 000000001010 (n << 3) + (n << 1) 000000001100 (n << 3) + (n << 2) 000000001110 (n << 4) - (n << 1) 000000001111 (n << 4) - n 000000010000 (n << 4) 000000010001 (n << 4) + n 000000010010 (n << 4) + (n << 1) 000000010100 (n << 4) + (n << 2) 000000011000 (n << 4) + (n << 3) 000000011100 (n << 5) - (n << 2) 000000011110 (n << 5) - (n << 1) 000000011111 (n << 5) - n 000000100000 (n << 5) 000000100001 (n << 5) + n 000000100010 (n << 5) + (n << 1) 000000100100 (n << 5) + (n << 2) 000000101000 (n << 5) + (n << 3) 000000110000 (n << 5) + (n << 4) 000000111000 (n << 6) - (n << 3) 000000111100 (n << 6) - (n << 2) 000000111110 (n << 6) - (n << 1) 000000111111 (n << 6) - n 000001000000 (n << 6) 000001000001 (n << 6) + n 000001000010 (n << 6) + (n << 1) 000001000100 (n << 6) + (n << 2) 000001001000 (n << 6) + (n << 3) 000001010000 (n << 6) + (n << 4) 000001100000 (n << 6) + (n << 5) 000001110000 (n << 7) - (n << 4) 000001111000 (n << 7) - (n << 3) 000001111100 (n << 7) - (n << 2) 000001111110 (n << 7) - (n << 1) 000001111111 (n << 7) - n 000010000000 (n << 7) 000010000001 (n << 7) + n 000010000010 (n << 7) + (n << 1) 000010000100 (n << 7) + (n << 2) 000010001000 (n << 7) + (n << 3) 000010010000 (n << 7) + (n << 4) 000010100000 (n << 7) + (n << 5) 000011000000 (n << 7) + (n << 6) 000011100000 (n << 8) - (n << 5) 000011110000 (n << 8) - (n << 4) 000011111000 (n << 8) - (n << 3) 000011111100 (n << 8) - (n << 2) 000011111110 (n << 8) - (n << 1) 000011111111 (n << 8) - n 000100000000 (n << 8) 000100000001 (n << 8) + n 000100000010 (n << 8) + (n << 1) 000100000100 (n << 8) + (n << 2) 000100001000 (n << 8) + (n << 3) 000100010000 (n << 8) + (n << 4) 000100100000 (n << 8) + (n << 5) 000101000000 (n << 8) + (n << 6) 000110000000 (n << 8) + (n << 7) 000111000000 (n << 9) - (n << 6) 000111100000 (n << 9) - (n << 5) 000111110000 (n << 9) - (n << 4) 000111111000 (n << 9) - (n << 3) 000111111100 (n << 9) - (n << 2) 000111111110 (n << 9) - (n << 1) 000111111111 (n << 9) - n 001000000000 (n << 9) 001000000001 (n << 9) + n 001000000010 (n << 9) + (n << 1) 001000000100 (n << 9) + (n << 2) 001000001000 (n << 9) + (n << 3) 001000010000 (n << 9) + (n << 4) 001000100000 (n << 9) + (n << 5) 001001000000 (n << 9) + (n << 6) 001010000000 (n << 9) + (n << 7) 001100000000 (n << 9) + (n << 8) 001110000000 (n << 10) - (n << 7) 001111000000 (n << 10) - (n << 6) 001111100000 (n << 10) - (n << 5) 001111110000 (n << 10) - (n << 4) 001111111000 (n << 10) - (n << 3) 001111111100 (n << 10) - (n << 2) 001111111110 (n << 10) - (n << 1) 001111111111 (n << 10) - n 010000000000 (n << 10) 010000000001 (n << 10) + n 010000000010 (n << 10) + (n << 1) 010000000100 (n << 10) + (n << 2) 010000001000 (n << 10) + (n << 3) 010000010000 (n << 10) + (n << 4) 010000100000 (n << 10) + (n << 5) 010001000000 (n << 10) + (n << 6) 010010000000 (n << 10) + (n << 7) 010100000000 (n << 10) + (n << 8) 011000000000 (n << 10) + (n << 9) 011100000000 (n << 11) - (n << 8) 011110000000 (n << 11) - (n << 7) 011111000000 (n << 11) - (n << 6) 011111100000 (n << 11) - (n << 5) 011111110000 (n << 11) - (n << 4) 011111111000 (n << 11) - (n << 3) 011111111100 (n << 11) - (n << 2) 011111111110 (n << 11) - (n << 1) 011111111111 (n << 11) - n 100000000000 (n << 11) 100000000001 (n << 11) + n 100000000010 (n << 11) + (n << 1) 100000000100 (n << 11) + (n << 2) 100000001000 (n << 11) + (n << 3) 100000010000 (n << 11) + (n << 4) 100000100000 (n << 11) + (n << 5) 100001000000 (n << 11) + (n << 6) 100010000000 (n << 11) + (n << 7) 100100000000 (n << 11) + (n << 8) 101000000000 (n << 11) + (n << 9) 110000000000 (n << 11) + (n << 10) 1000000000000 (n << 11) + (n << 11)

As you can see, on the left most column, a simple multiplication formula is given, which can also be expresed by the right most column. The basic approach was already discussed in the prior article, where I developed the following relation:

`(2x - 2y) * n ≙ (n << x) - (n << y)`

I want to give you an example which is not so trivial on the first sight. Please consider the equation 496 * n. The table above says, we can describe 496 by 29 - 24, so that we could use the formula

`(n << 9) - (n << 4)`

... and after the reshaping, we'll get the same result as with a perhaps slower multiplication. Of course, the trick will only bring a performance benefit, if the architecture uses a slow multiplication implementation and fast binary/subtraction operations.

You might also be interested in the following