Boost logo

Boost :

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


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk