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