Re: [boost] Large Integer Library

Subject: Re: [boost] Large Integer Library
From: Steven Watanabe (watanabesj_at_[hidden])
Date: 2012-06-30 16:04:15

AMDG

On 06/30/2012 12:47 PM, Michael Tryhorn wrote:
> Dear all,
> 
> Some responses to questions asked so far:
> 
>> That can't be right.  Addition of two n-bit numbers requires
>> processing all n bits and is therefore O(n).  The fastest
>> known algorithm for multiplying two n-bit numbers is slower
>> than O(n).
> 
> I may be wrong, but my understanding was that at least for an
> addition operation, while certainly implemented via adders in
> hardware (and hence O(n)), we would not call it so in algorithms
> that use it.  Let me give an example.  If I wrote a function
> thus:
> 
> int add_these(int a, int b)
> {
>     return a+b;
> }
> 
> I would expect that rather than converting my '+' to a loop,
> the compiler would turn it into assembly 'LOAD/ADD/STORE'.  My
> evaluation of the complexity of the above algorithm itself (if
> we can call it such) would be to label it 'O(1)' rather than 'O(n)'.
> For reference, let me quote the code from large_int::operator+= :
> 
> large_int<T, U>& large_int<T, U>::operator+= (const this_type& val)
> {
>     // Take a copy of *this, to modify
>     this_type ret(*this);
> 
>     // Perform the addition
>     ret.m_lo += val.m_lo;
>     ret.m_hi += val.m_hi;
>     if( ret.m_lo < m_lo )
>     {
>         ++ret.m_hi;
>     }
> 
>     // Commit the result
>     return( *this = ret );
> }
> 
> Although a little more complex, additions should only ever perform a
> single pass of this function.  As for multiplication, the operator*=
> implementation uses a for loop which loops at most 'n' times, where
> 'n' is the number of binary bits in the integer, making use of +=
> (above) and the shift operators.
> 

You're being inconsistent about whether
the number of bits is a constant.  The
number of operations is O(d) where d is
the number of built-in integers in the
argument after expanding large_int recursively.
Since the number of bits in a built-in
integer type is a constant, O(d) = O(n).

In Christ,
Steven Watanabe