Re: [boost] Large Integer Library

Subject: Re: [boost] Large Integer Library
From: Marc Glisse (marc.glisse_at_[hidden])
Date: 2012-06-30 16:10:10

On Sat, 30 Jun 2012, Michael Tryhorn wrote:

>> 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)'.

Yes.

> 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 );
> }

So when you add numbers of 2n bits, you perform 2 additions of numbers of 
n bits, plus a comparison and an increment.
A(2n) <= 2*A(n) + n
so A(n) = O(n*log(n))
(I haven't checked whether the bound is tight or the true complexity is 
log(n))

For a fixed n, O(1)=O(n), complexities are about how things grow with n.

> 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.

About the multiplication, maybe you could try using the n x n 
multiplication in the implementation of the 2n x 2n multiplication?

>> The typedef for l[u]int128_t

By the way, why the 'l' prefix?

>> I had "undefined symbol" problems when using the builtin 128 bits
>> integers (provided by gcc) in the signature of functions in a shared
>> library (it was a module created with Boost.Python, the problem occurred
>> when importing this module within python). The only solution I found was
>> to wrap integer-like types inside a (templated) class, which looks like a
>> particular case of your library (this would be "large_int<EMPTY_TYPE,
> U>").

Sounds like you think there is a bug in the compiler. Did you file a 
report?

-- 
Marc Glisse