On Wed, 18 Oct 2000, Riad S. Wahby wrote:
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)).
Actually, even that's not quite true. Carry lookahead guarantees worst-case performance on addition of O(log2 N) where N is the size of the numbers being addded. However, there is a "shortcut" available, on average, once per 2 bits in the addition where the carry can be determined fully even before carry-lookahead gets there. These are the "base cases" of carry lookahead, where both operand bits are equal to one, or both operand bits are equal to zero. You don't need to determine the carry into those places to determine the carry bits out of them. This means that you can build hardware, in practice, that does addition in an average case proportional to the log of the distance between (1,1)pairs in the operands. In the worst case, that's (log2 N) but in the average case it's (Log2 (log2 N)). The downside of this is that it involves an O((2^N)/N) number of gates, where conventional carry lookahead involves only O(N^2) number of gates, and that it makes the amount of time required to complete an addition depend on the arguments. Chip designers generally don't do this, more because of the second reason than the first. :-) Math, anyone? Bear