# 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