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