Sampo A Syreeni <ssyreeni@cc.helsinki.fi> wrote:
I think addition is bounded by something more like o(n) - carry propagation limits it. Anyway, your point is accurate. There are proven NP-hard problems and there have even been attempts to find ones with easy inverses for use in crypto. I don't think any of them have succeeded.
If you're talking about the carries actually falling through full adders, there is a method called carry lookahead that computes carries in a tree (with branching factor 2). Computing the sum bits from the carries is a constant time independent of the number of bits in the adder, so the process is overall Theta(log(N)). On the other hand, if you're talking about speed of propagation through traces, you're right for large gate size. However, as gates get smaller, the speed of propagation becomes less important, and the adder speed asymptotically approaches Theta(log(N)). -- Riad Wahby rsw@mit.edu MIT VI-2/A 2002 5105