Most efficient circuit for 2048 Bit multiplication, and how to effectively render it

So this isn't for a hardware application, but I still think it will be extremely relevant to those that are chip designers/EE enthusiasts.

I'm attempting to do some analysis on multiplication viewed as a boolean function. For this I want to construct a boolean function of two vectors $X,Y$ each of length 2048. Of course a symbolic representation of this function corresponds to an actual circuit, so implicitly what I want to do is build the smallest possible circuit (meaning fewest number of gates followed by least depth) for multiplying two 2048 bit numbers and store the result in a text file (using And and NOT and Or)

Now with this comes a couple of parts:

1. Choice of algorithm: I'm thinking building the circuit implementing Karatsuba's algorithm would be a good idea (is 2048 bits large enough to warrant Toom-Cook?, I know its definitely too small for Strassen's Fourier Transform techniques).

2. Switching between algorithms, there should exist some value N, for which multiplication of N digit numbers is faster through traditional grade-school style multiplication, than running up my costs by implementing Karatsuba style multipliers at that level.

3. Once I have the algorithm built out what is the best way to render it symbolically in a text file? My gut is to hack this out with a long script, but perhaps you might know of some tools that let you abstractly generate circuits and write out the results which would be faster for me to convert to my desired forms than trying to reinvent the wheel in python.

• You won't be able to do it using AND and OR only. You'll need also NOT. Alternatively you can do it using only NAND (or NOR). Funny old world. – Tom Carpenter Aug 13 '16 at 1:22
• Ah yes, in willing to allow NOTs as well, my mistake for missing that in the text – frogeyedpeas Aug 13 '16 at 1:28
• First you say you want least number of gates, then maybe least depth. Then you say you wan it "faster". You should pick one dimension to optimize, or define a cost function, or a dimension to optimize with limits on the other parameters. You can't simultaneously optimize speed and number of gates, for sure. – The Photon Aug 13 '16 at 1:35
• Engineering doesn't work with casual terms. To get a answer that meets your needs, you need to be clear what your needs are. Least gate count will probably be something like processing the bits serially, and will be very slow. – The Photon Aug 13 '16 at 2:00
• 3sat hmm, not wanting to factor large composites are you? – Jasen Aug 13 '16 at 3:36

1 Answer

Firstly, it depends what the rest of your hardware is. Is it just the multiplier, or is there some other hardware, e.g. memory controllers etc., that is going to be needed anyway and you can utilize. Secondly, do you have a floor in performance? I can think of small multiplier implementations that will be quite slow?

Off the top of my head, there are 8051 implementations that are below 3000 gates. Remove pipelining, and all the unused instructions and hardware, and you can have an MCU that is a few hundred logic gates. Now, add some RAM and you have your very low gate multiplier.

I think the smallest implementation will involve a very minimal ALU with the following operations: add, shift, and XOR. This is all you need to implement the multiplication. You can use RAM to store your data. Add a few instructions and a basic control unit, and you have a rudimentary processor. You then off load all the complexity in the form of instructions.

Also, what do you count as a gate? Are you after minimum logic gate count, or minimum transistor count? What about flip-flops? Different answers to these questions can produce very different results.

• This won't be used by any hardware, it needs to be single cycle, a gate is any K-input (AND, OR, NOR, NAND) – frogeyedpeas Sep 1 '16 at 16:31
• I'm after minimizing logic gate count, this "circuit" happens to be of value in analyzing a problem through my particular means, – frogeyedpeas Sep 1 '16 at 16:33