CDR: Re: why should it be trusted?

[Ray Dillinger]

On Wed, 18 Oct 2000, Riad S. Wahby wrote:

>Sampo A Syreeni <ssyreeni at 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