Complexity of Arithmetic Circuits

[sou123]

Hi everyone,

 

I have seen that while designing arithmetic circuits such as adder etc, people say that this adder is of complexity O(n) or O(n^2) or something like that. My question is, given a circuit, how can I find its complexity?

Is there any book chapter or paper that addresses this issue from the basics.

 

Thanking in advance.

[Enthalpy]

No hope!

 

Complexity has to be proven for individual cases, and there is no general method for the proof. This stands for circuits exactly as for algorithms.

 

Just one example: factorization of big numbers has been investigated since antiquity, is vital to every credit card or https data exchange, but we only suppose that factoring is difficult - no proof exists other than the lack of a good method up to now.

 

This is not just a theoretical question! For instance, multiplication of big numbers seems to be of N^2 complexity, but it can be done by a Fourier transform in N*Log(N) complexity - and is done to compute Pi quickly, for instance by the programme Superpi. Same for convolution, for antivirus parsing...

 

Arithmetic circuits have the added difficulty of being too small for O(something) complexity to be meaningful. Take the lookahead carry of a 16 bit adder for instance: it has 1 level only, sometimes 2. General considerations will be overshadowed by detail considerations.

 

You could read Dijkstra about arithmetic circuits, I think his book is "seminumerical algorithms". Pre-Apollo era but still actual. Some more, in software but transposable, in "numerical reciepes in C".

 

The good side of this: no room for a method means room for intelligence.