# 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 | 000000000000 | n - n |
---|---|---|

1 * n | 000000000001 | n |

2 * n | 000000000010 | (n << 1) |

3 * n | 000000000011 | (n << 1) + n |

4 * n | 000000000100 | (n << 2) |

5 * n | 000000000101 | (n << 2) + n |

6 * n | 000000000110 | (n << 2) + (n << 1) |

7 * n | 000000000111 | (n << 3) - n |

8 * n | 000000001000 | (n << 3) |

9 * n | 000000001001 | (n << 3) + n |

10 * n | 000000001010 | (n << 3) + (n << 1) |

12 * n | 000000001100 | (n << 3) + (n << 2) |

14 * n | 000000001110 | (n << 4) - (n << 1) |

15 * n | 000000001111 | (n << 4) - n |

16 * n | 000000010000 | (n << 4) |

17 * n | 000000010001 | (n << 4) + n |

18 * n | 000000010010 | (n << 4) + (n << 1) |

20 * n | 000000010100 | (n << 4) + (n << 2) |

24 * n | 000000011000 | (n << 4) + (n << 3) |

28 * n | 000000011100 | (n << 5) - (n << 2) |

30 * n | 000000011110 | (n << 5) - (n << 1) |

31 * n | 000000011111 | (n << 5) - n |

32 * n | 000000100000 | (n << 5) |

33 * n | 000000100001 | (n << 5) + n |

34 * n | 000000100010 | (n << 5) + (n << 1) |

36 * n | 000000100100 | (n << 5) + (n << 2) |

40 * n | 000000101000 | (n << 5) + (n << 3) |

48 * n | 000000110000 | (n << 5) + (n << 4) |

56 * n | 000000111000 | (n << 6) - (n << 3) |

60 * n | 000000111100 | (n << 6) - (n << 2) |

62 * n | 000000111110 | (n << 6) - (n << 1) |

63 * n | 000000111111 | (n << 6) - n |

64 * n | 000001000000 | (n << 6) |

65 * n | 000001000001 | (n << 6) + n |

66 * n | 000001000010 | (n << 6) + (n << 1) |

68 * n | 000001000100 | (n << 6) + (n << 2) |

72 * n | 000001001000 | (n << 6) + (n << 3) |

80 * n | 000001010000 | (n << 6) + (n << 4) |

96 * n | 000001100000 | (n << 6) + (n << 5) |

112 * n | 000001110000 | (n << 7) - (n << 4) |

120 * n | 000001111000 | (n << 7) - (n << 3) |

124 * n | 000001111100 | (n << 7) - (n << 2) |

126 * n | 000001111110 | (n << 7) - (n << 1) |

127 * n | 000001111111 | (n << 7) - n |

128 * n | 000010000000 | (n << 7) |

129 * n | 000010000001 | (n << 7) + n |

130 * n | 000010000010 | (n << 7) + (n << 1) |

132 * n | 000010000100 | (n << 7) + (n << 2) |

136 * n | 000010001000 | (n << 7) + (n << 3) |

144 * n | 000010010000 | (n << 7) + (n << 4) |

160 * n | 000010100000 | (n << 7) + (n << 5) |

192 * n | 000011000000 | (n << 7) + (n << 6) |

224 * n | 000011100000 | (n << 8) - (n << 5) |

240 * n | 000011110000 | (n << 8) - (n << 4) |

248 * n | 000011111000 | (n << 8) - (n << 3) |

252 * n | 000011111100 | (n << 8) - (n << 2) |

254 * n | 000011111110 | (n << 8) - (n << 1) |

255 * n | 000011111111 | (n << 8) - n |

256 * n | 000100000000 | (n << 8) |

257 * n | 000100000001 | (n << 8) + n |

258 * n | 000100000010 | (n << 8) + (n << 1) |

260 * n | 000100000100 | (n << 8) + (n << 2) |

264 * n | 000100001000 | (n << 8) + (n << 3) |

272 * n | 000100010000 | (n << 8) + (n << 4) |

288 * n | 000100100000 | (n << 8) + (n << 5) |

320 * n | 000101000000 | (n << 8) + (n << 6) |

384 * n | 000110000000 | (n << 8) + (n << 7) |

448 * n | 000111000000 | (n << 9) - (n << 6) |

480 * n | 000111100000 | (n << 9) - (n << 5) |

496 * n | 000111110000 | (n << 9) - (n << 4) |

504 * n | 000111111000 | (n << 9) - (n << 3) |

508 * n | 000111111100 | (n << 9) - (n << 2) |

510 * n | 000111111110 | (n << 9) - (n << 1) |

511 * n | 000111111111 | (n << 9) - n |

512 * n | 001000000000 | (n << 9) |

513 * n | 001000000001 | (n << 9) + n |

514 * n | 001000000010 | (n << 9) + (n << 1) |

516 * n | 001000000100 | (n << 9) + (n << 2) |

520 * n | 001000001000 | (n << 9) + (n << 3) |

528 * n | 001000010000 | (n << 9) + (n << 4) |

544 * n | 001000100000 | (n << 9) + (n << 5) |

576 * n | 001001000000 | (n << 9) + (n << 6) |

640 * n | 001010000000 | (n << 9) + (n << 7) |

768 * n | 001100000000 | (n << 9) + (n << 8) |

896 * n | 001110000000 | (n << 10) - (n << 7) |

960 * n | 001111000000 | (n << 10) - (n << 6) |

992 * n | 001111100000 | (n << 10) - (n << 5) |

1008 * n | 001111110000 | (n << 10) - (n << 4) |

1016 * n | 001111111000 | (n << 10) - (n << 3) |

1020 * n | 001111111100 | (n << 10) - (n << 2) |

1022 * n | 001111111110 | (n << 10) - (n << 1) |

1023 * n | 001111111111 | (n << 10) - n |

1024 * n | 010000000000 | (n << 10) |

1025 * n | 010000000001 | (n << 10) + n |

1026 * n | 010000000010 | (n << 10) + (n << 1) |

1028 * n | 010000000100 | (n << 10) + (n << 2) |

1032 * n | 010000001000 | (n << 10) + (n << 3) |

1040 * n | 010000010000 | (n << 10) + (n << 4) |

1056 * n | 010000100000 | (n << 10) + (n << 5) |

1088 * n | 010001000000 | (n << 10) + (n << 6) |

1152 * n | 010010000000 | (n << 10) + (n << 7) |

1280 * n | 010100000000 | (n << 10) + (n << 8) |

1536 * n | 011000000000 | (n << 10) + (n << 9) |

1792 * n | 011100000000 | (n << 11) - (n << 8) |

1920 * n | 011110000000 | (n << 11) - (n << 7) |

1984 * n | 011111000000 | (n << 11) - (n << 6) |

2016 * n | 011111100000 | (n << 11) - (n << 5) |

2032 * n | 011111110000 | (n << 11) - (n << 4) |

2040 * n | 011111111000 | (n << 11) - (n << 3) |

2044 * n | 011111111100 | (n << 11) - (n << 2) |

2046 * n | 011111111110 | (n << 11) - (n << 1) |

2047 * n | 011111111111 | (n << 11) - n |

2048 * n | 100000000000 | (n << 11) |

2049 * n | 100000000001 | (n << 11) + n |

2050 * n | 100000000010 | (n << 11) + (n << 1) |

2052 * n | 100000000100 | (n << 11) + (n << 2) |

2056 * n | 100000001000 | (n << 11) + (n << 3) |

2064 * n | 100000010000 | (n << 11) + (n << 4) |

2080 * n | 100000100000 | (n << 11) + (n << 5) |

2112 * n | 100001000000 | (n << 11) + (n << 6) |

2176 * n | 100010000000 | (n << 11) + (n << 7) |

2304 * n | 100100000000 | (n << 11) + (n << 8) |

2560 * n | 101000000000 | (n << 11) + (n << 9) |

3072 * n | 110000000000 | (n << 11) + (n << 10) |

4096 * n | 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:

(2^{x}- 2^{y}) * 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 2^{9} - 2^{4}, 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

- Optimized Pagination using MySQL
- Optimal index size for variable text in MySQL
- Store small numbers in big numbers
- My very first Chrome experiment

**Sorry, comments are closed for this article. Contact me if you want to leave a note.**