First page Back Continue Last page Overview Graphics

Binary Multiplication

Notes:

Binary multiplication is a more complicated circuit, but can multiply bigger numbers with less tape and fewer time steps. Six solutions are shown, from a 3-bit x 3-bit multiplier. Can you figure out the logic? It's standard grade-school multiplication. Green and blue cells represent the input numbers, red the accumulated result. (Exercise: write the one-step FST for this circuit.)

The binary circuit's time and space advantages don't come for free. In the unary circuit the number of possible flight sequences for each line was quadratic in the length of the tape: there was one transition from red to blue, and one from blue to gray. But the binary multiplier has choices of 0 or 1 for each cell, exponential in the length of the tape. Thus there are exponentially greater many flight sequences to search over. As of September, 2003 the ITA Software search engine maxes out its search capabilities at 4-bit multiplication – the times table up to 15 times 15, with 130 flights and fares per solution.